¿Soy solo yo o el algoritmo recursivo de Fibonacci es brillantemente complejo?

Creo lo contrario: la mayoría de los algoritmos recursivos son soluciones brillantes y simples para problemas complejos. De todos modos, antes de comenzar, debemos definir a qué secuencia de Fibonacci nos referimos, ya que hay variantes basadas en cómo iniciar la secuencia y cómo indexar los números. Nuestra definición será: [matemáticas] F_0 = 1 [/ matemáticas], [matemáticas] F_1 = 1 [/ matemáticas], [matemáticas] F_2 = 2 [/ matemáticas], [matemáticas] F_3 = 3 [/ matemáticas], … , [matemáticas] F_n = F_ {n-2} + F_ {n-1} [/ matemáticas].

El algoritmo iterativo es claramente [matemática] O (n) [/ matemática] ya que necesitamos variar el valor de una variable de índice de 2 a [matemática] n-1 [/ matemática] para determinar los valores de [matemática ] F_2 [/ matemáticas], [matemáticas] F_3 [/ matemáticas],…, [matemáticas] F_ {n-1} [/ matemáticas]. El problema con la solución recursiva es que gasta una cantidad significativa de tiempo recalculando resultados anteriores. Aquí está el código C,

long fib (long n) / * calcula y devuelve el enésimo número de Fibonacci * /
{
if (n <0) error ();
sino si (n <2) devuelve 1;
de lo contrario, devuelve fib (n-2) + fib (n-1);
}

Para determinar la complejidad del tiempo algorítmico, deje que [math] fib (n-2) + fib (n-1) [/ math] sea la operación clave. El siguiente paso en el análisis es encontrar una función [matemática] f (n) [/ matemática] que cuente cuántas veces se realiza la operación de tecla en función de [matemática] n [/ matemática]. Encuentro que hacer una tabla es muy útil para identificar los patrones en este tipo de problemas,

nf (n)
0 0
1 0
2 1
3 2
4 3
5 5
6 8

Es interesante observar que [math] f (n) [/ math] también sigue la secuencia de Fibonaci. No es terriblemente difícil demostrar que [matemáticas] f (n) \ aprox {{\ phi ^ n} \ over {\ sqrt {5}}} [/ matemáticas] (consulte un libro de texto decente de matemáticas discretas para la prueba) donde [math] \ phi [/ math] es la conocida Golden Ratio, que es aproximadamente 1.62. Es sencillo usar [math] f (n) [/ math] y mostrar que nuestra función fib() es [math] O (\ phi ^ n) [/ math], que es una complejidad exponencial. Por lo tanto, no solo es fib() recursivo fib() más lento que fib() iterativo, sino que es sustancialmente más lento, tanto que solo para valores medianos de n , fib() recursivo fib() no se completará en muchos, muchos años.

Referencias

Wolfram MathWorld: Número de Fibonacci

Wolfram MathWorld: Golden Ratio – de Wolfram MathWorld

La recursión es una herramienta descriptiva que implica retroalimentación, al igual que una ecuación diferencial, por lo que es más alucinante cuando se inicia.

Si un problema es recursivo por naturaleza, es difícil no describirlo por recursividad, al igual que el número de Fibonacci. Lo mismo que un problema diferencial se describe mejor mediante una ecuación diferencial.

Pero encontrar el término número 100 del número de Fibonacci por método recursivo no es en absoluto más brillante que encontrar el término número 100 de una suma aritmética por método de iteración. Porque al igual que la suma aritmética se puede encontrar por [math] \ dfrac {n (n + 1)} {2} [/ math], la forma cercana del número de Fibonacci es [math] \ dfrac {(\ frac {1+ \ sqrt {5}} {2}) ^ n – (\ frac {1- \ sqrt {5}} {2}) ^ n} {\ sqrt {5}} [/ math]. Un curso de nivel universitario enseña cómo encontrar la forma cercana de una ecuación recursiva, como el material del libro “Matemáticas concretas” de Graham, Knuth y Patashnik.