Cálculo da sequência de fibonacci na prática
A sequência de fibonacci é uma progressão em que cada termo é a soma dos dois anteriores, começando com 0 e 1. A relação de recorrência é simples: F(n) = F(n-1) + F(n-2). Parece trivial até você tentar calcular F(50) com recursão ingênua e esperar que o computador termine antes do fim do mundo. Eu já vi gente implementar isso como exercício de introdução à programação sem perceber que a complexidade exponencial vai explodir a partir de n=35 ou 40 em uma implementação recursiva pura. O tempo de execução dobra a cada incremento. Não é um problema de hardware, é um problema estrutural do algoritmo.
O jeito certo de fazer isso depende do que você precisa. Se quer apenas os primeiros termos, iteração com duas variáveis resolve em tempo linear e espaço constante. Você mantém dois acumuladores e vai somando até chegar onde precisa. Fácil, rápido, sem surpresas.
O que realmente preciso saber sobre a sequência de fibonacci
O problema que me fez parar e pensar diferente sobre isso foi quando precisei calcular F(n) para n na casa de milhares, num projeto de criptografia. A abordagem iterativa comum funciona bem até certo ponto, mas a partir de n=10.000 você começa a lidar com números enormes — F(10.000) tem mais de 2.000 dígitos decimais. A simples soma de inteiros normais não cabe mais em variáveis padrão. Minha solução foi usar exponenciação de matrizes combinada com aritmética de big integers. A identidade matricial [1,1; 1,0]^n = [F(n+1), F(n); F(n), F(n-1)] permite calcular qualquer termo em tempo logarítmico, O(log n), em vez do tempo linear da iteração simples. Para n=100.000, isso fez a diferença entre minutos e segundos, considerando ainda o custo das operações com números grandes.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Aqui está a parte que poucos mencionam: a fórmula de Binet, aquela que usa a razão áurea elevando n ao poder e dividindo pela raiz de 5, parece elegante mas é numericamente instável para valores maiores de n. A partir de n=71 ou 72 em precisão dupla, o arredondamento do float já erra o resultado. Já perdi horas debuggando isso achando que o código estava errado quando na verdade era apenas o (float) que falhando. Outro detalhe prático: se o seu uso envolve módulo — o que é comum em competições de programação ou algoritmos criptográficos — você pode aplicar o módulo em cada passo da soma e manter os números sempre pequenos. Isso se chama propriedade de Pisano. A sequência de fibonacci módulo m é periódica, e o período (chamado período de Pisano) para m=10^9+7 é algo em torno de 2·10^9, então isso só ajuda se você souber antecipar o tamanho do módulo e o valor de n que vai precisar.
Se você só precisa gerar os primeiros 50 ou 100 termos para um exercício ou protótipo, um loop simples em Python ou qualquer linguagem basta. Se o objetivo é calcular F(n) para n alto com precisão exata, use exponenciação de matrizes com bibliotecas de big int. E se o contexto é algorítmico com modulo, memoização por matriz ou o método de doubling formulas são mais eficientes que iteração pura. Os doubling formulas permitem calcular F(2k) e F(2k+1) a partir de F(k): F(2k) = F(k) · [2·F(k+1) - F(k)] e F(2k+1) = F(k+1)^2 + F(k)^2. É basicamente a mesma ideia da exponenciação de matrizes mas operando diretamente sobre os termos, e costuma ser um pouco mais rápido na prática porque evita a sobrecarga da multiplicação de matrizes 2x2.
Não existe solução mágica. Cada abordagem tem um trade-off claro entre velocidade, precisão e memória. Escolha a que se encaixa no seu caso e teste com valores conhecidos antes de confiar no resultado.
