FIBONACCI

Números de Fibonacci, su complejidad y su programación.
La llamada sucesión de los números de Fibonacci
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
que aparece por primera vez en el célebre, Liber abaci(1202), publicado por Leonardo Pisano, como solución a un problema de reproducción de conejos, satisface la ecuación en recurrencia lineal
Fn = Fn-1 + Fn-2
donde F1 = 1 = F2
Cláramente, no es laúnica sucesión de números, solución de la misma ecuación en recurrencia. Por ejemplo, la sucesión
1, 3, 4, 7, 11, 18, 29, 47, 76, ...
llamados los números de Lucas (matemático francés, 1842-1891).También satisfacen la misma ecuación en recurrencia. Pero la diferencia está en los dos primeros términos, que en este caso son F1 = 1 ; F2 = 3.
Como los siguientes valores de una tal sucesión F1, F2, F3,... están determinados por los dos primeros. Hay tantas sucesiones solución como parejas de números F1 = a ; F2 = b.
Programación recursiva.
Si queremos programar una función que calcule el n-ésimotérmino, Fn, de una de estas soluciones. La primera aproximación es precísamente recursiva. Por ejemplo, hoy día, casi todos los lenguajes de alto nivel, admiten las tres siguientes líneas que implementanel cálculo de los números de Fibonacci, con pocas diferencias de sintaxis
F(1) = 1;
F(2) = 1;
F(n) = F(n-1) + F(n-2);
El problema es su complejidad. No sólo en espacio. Ya que todas las llamadasanteriores, a la propia función, han de recordarse, calcularse y asignarse para poder hallar F(n). Sino también en número de operaciones elementales. Que se traduce en complejidad de tiempo. Ya que sesuman todas las operaciones elementales necesarias para calcular todos los anteriores.
Complejidad.

Pero ¿Cómo de rápido crece la función de Fibonacci?.
Para responder a esa pregunta. Calcularemos lasraíces de la ecuación característica asociada a la ecuación en recurrencia F(n) = F(n-1) + F(n-2).
x2 = x + 1
o sea, las raíces de x2 - x - 1 = 0

Una de ellas, es el llamado número de oro...