Generador de Fibonacci

La sucesión de Fibonacci es una serie donde cada número es la suma de los dos anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... Lleva el nombre de Leonardo de Pisa (Fibonacci), quien la introdujo en las matemáticas europeas en 1202 a través de su libro Liber Abaci. La sucesión aparece en la naturaleza: la disposición espiral de las semillas de girasol, las escamas de los piñones, la filotaxis de las hojas, las conchas de nautilo y la ramificación de los árboles.

La proporción áurea (φ ≈ 1,6180339887...) es el límite de F(n+1)/F(n) cuando n tiende a infinito. El valor exacto es (1 + √5) / 2. Dos cantidades están en proporción áurea si su razón es igual a la razón de su suma con la cantidad mayor: (a+b)/a = a/b = φ. La proporción áurea aparece en la geometría euclídea, el arte, la arquitectura (Partenón) y ha fascinado a los matemáticos durante siglos.

El número de espirales en girasoles, piñones y piñas son números de Fibonacci consecutivos (típicamente 21 y 34, o 34 y 55). El número de pétalos en muchas flores es un número de Fibonacci (3, 5, 8, 13). Las disposiciones de hojas en los tallos siguen fracciones de Fibonacci para maximizar la exposición al sol. El modelo de población de conejos que Fibonacci usó para introducir la sucesión: si un par de conejos produce una nueva pareja cada mes a partir del segundo mes, la población crece siguiendo la sucesión de Fibonacci.

Recursión naive: O(2^n) — tiempo exponencial. Recursión memoizada o iteración: O(n). Exponenciación matricial: O(log n). Fórmula cerrada de Binet: F(n) = (φ^n − ψ^n) / √5 donde ψ = (1−√5)/2 — teóricamente O(1) pero pierde precisión para n grande por errores de coma flotante. Para números de Fibonacci grandes exactos, use aritmética de enteros de precisión arbitraria (int de Python, BigInteger de Java).

Montículos de Fibonacci (usados en el algoritmo de Dijkstra), búsqueda de Fibonacci (alternativa a la búsqueda binaria), generadores de números pseudoaleatorios, el teorema de Zeckendorf (todo entero positivo se representa únicamente como suma de números de Fibonacci no consecutivos), codificación de Fibonacci (código universal para compresión de enteros), generación de nivel aleatorio en listas de salto y análisis de entradas en el peor caso para ciertos algoritmos como el GCD de Euclides.