Gerador de Fibonacci

A sequência de Fibonacci é uma série em que cada número é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... Nomeada em homenagem a Leonardo de Pisa (Fibonacci), que a introduziu na matemática europeia em 1202 por meio do seu livro Liber Abaci. A sequência aparece na natureza: o arranjo espiral das sementes de girassol, as escamas de pinha, a filotaxia das folhas, as conchas de nautilus e a ramificação das árvores.

A razão áurea (φ ≈ 1,6180339887...) é o limite de F(n+1)/F(n) quando n tende ao infinito. O valor exato é (1 + √5) / 2. Duas quantidades estão na razão áurea se sua razão é a mesma que a razão de sua soma para a maior quantidade: (a+b)/a = a/b = φ. A razão áurea aparece na geometria euclidiana, arte, arquitetura (Partenon) e fascina matemáticos há séculos. Ela também está relacionada ao pentágono regular e ao icosaedro.

O número de espirais em girassóis, pinhas e abacaxis são números de Fibonacci consecutivos (tipicamente 21 e 34, ou 34 e 55). O número de pétalas em muitas flores é um número de Fibonacci (3, 5, 8, 13). Os arranjos de folhas nos caules seguem frações de Fibonacci para maximizar a exposição solar. O modelo de população de coelhos que Fibonacci usou para apresentar a sequência: se um par de coelhos produz um novo par a cada mês, a partir do segundo mês, a população cresce seguindo a sequência de Fibonacci.

Recursão ingênua: O(2^n) — tempo exponencial. Recursão com memoização ou iteração: O(n). Exponenciação de matrizes: O(log n). Fórmula fechada de Binet: F(n) = (φ^n − ψ^n) / √5, onde ψ = (1−√5)/2 — teoricamente O(1), mas perde precisão para n grande devido a erros de ponto flutuante. Para números de Fibonacci grandes exatos, use aritmética inteira de precisão arbitrária (int do Python, BigInteger do Java). F(100) tem 21 dígitos; F(1000) tem 209 dígitos.

Heaps de Fibonacci (usados no algoritmo de Dijkstra), busca de Fibonacci (alternativa à busca binária), geradores de números pseudoaleatórios, teorema de Zeckendorf (todo inteiro positivo é representável de forma única como soma de números de Fibonacci não consecutivos), codificação de Fibonacci (código universal para compressão de inteiros), geração de nível aleatório em skip lists, e análise de entradas de pior caso para certos algoritmos como o algoritmo GCD de Euclides.