Google y la recursión

Esto que les cuento hoy apareció como noticia en El País hace unos días.
Vamos a hacer un experimento. Abra en otra ventana del navegador la pagina de Google y escriba Varcelona, así, con V de Varsovia. Obtendrá un montón de resultados de búsqueda, pero a lo que vamos es lo que sale arriba:Si Google detecta que la palabra de búsqueda está mal escrita nos propone corregirla.
Quizás quiso decir: Barcelona.
Y si pinchamos en la sugerencia, esta desaparece.

Ahora repitan lo mismo con la palabra Recursión. Google nos propone que hagamos la búsqueda por el término Recursión, pero cuando pinchamos en la sugerencia, la misma sugerencia vuelve a salir, una y otra vez, hasta el infinito.

Esto es una broma de los programadores de Google que muestra el fino sentido del humor que gastan. Vamos a intentar entender el chiste.

En matemáticas se llama recursión o recursividad (dos palabros que no existen en español, por cierto. El término correcto es recurrencia) a una manera de escribir sucesiones de números en la que cada término se calcula a partir de los anteriores.
Por ejemplo, la famosísima sucesión de Fibonacci:
1, 1, 2, 3, 5, 8, 13, 21, ...
en la que los dos primeros números son 1 y 1 y a partir de ahí cada uno de los elementos se calcula sumando los dos que tiene detrás.

1+1=2
1+2=3
2+3=5
3+5=8
5+8=13

La manera de escribir esto usando la recursión es:

F₀=1
F₁=1
F₂=F₀+F₁=1+1=2
F₃=F₁+F_2=1+2=3
...
F_n=F_n-2+F_n-1

Es decir, que para definir un elemento se hace referencia a la propia definición del elemento en casos mas pequeños, así hasta llegar al caso mas sencillo, que está definido numéricamente.
Por ejemplo: vamos a calcular F₅ , el 5º término de la sucesión de Fibonacci:

F₅=F₃+F₄

por lo tanto, hay que calcular primero el 3º y el 4º (o sea F₃ y F₄)

F₄=F₂+F₃
F₃=F₁+F₂

Con lo cual el 5º término sería (los paréntesis son sólo para separar y no liarnos):

F₅=(F₃)+(F₄)=
=(F₁+F₂)+(F₂+[F₃])=
=(F₁+F₂)+(F₂+[F₁+F₂])

Pero F₁=1 y F₂=1, así que para calcular F₅ basta con sustituir en la fórmula anterior:
F₅=(F₁+F₂)+(F₂+[F₁+F₂])
F₅= (1+1) + (1 + [1+1])=5

O sea, que para calcula un número utilizamos su propia definición tantas veces como haga falta hasta llegar al caso más sencillo. Intenten ustedes calcular otros términos por sí mismos, les ayudará a entenderlo.

El buscador de Google hace esto mismo: si se le pide que busque recursión nos propone que busquemos recursión, y si aceptamos la sugerencia nos vuelve a hacer la misma sugerencia, y así hasta el infinito.
Para Google, recursión es una recursión sin fin.

Nota: Esta forma de calcular es la que utilizan los ordenadores para hacer tareas complejas: Dividen la tarea en otras mas pequeñas recursivamente hasta llegar a un caso sencillo que pueden resolver fácilmente. Dos ejemplos:

1. La ordenación de un conjunto de números:
Para ordenar una lista de números se divide la lista en dos trozos, se ordenan cada uno por separado y luego se mezclan. Para ordenar cada uno de los trozos se utiliza el mismo procedimiento recursivo.
2. Buscar un número (o una palabra) en una lista no ordenada:
Se divide la lista en dos partes y se busca en una de ellas. Sino está se busca en la otra mitad. Cada una de las búsquedas se hace usando el mismo procedimiento. Aunque parezca mentira los ordenadores encuentran las cosas antes usando este método que mirando uno a uno los elementos de la lista.