A Sequência De Fibonacci

Implementando a sequência de Fibonacci na prática

A abordagem mais comum que eu vejo é a recursão ingênua. Você escreve a função que chama a si mesma duas vezes e resolve. Funciona para os primeiros termos, mas a partir do term 35 ou 40 o tempo de execução cresce de forma exponencial e você começa a esperar segundos pelo resultado. Eu parei de usar esse método faz anos. O jeito mais direto é iterativo. Você mantém dois acumuladores e avança posição por posição. Em JavaScript:

function fib(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}
Isso roda em tempo linear O(n) e usa memória constante. Para a maioria dos casos do dia a dia, esse é o suficiente.

O que todo mundo esquece sobre memoização

A memoização com cache funciona bem quando você precisa chamar a função várias vezes para valores diferentes, mas se você só precisa de um único termo, o overhead de manter um objeto cache na memória pode não valer a pena. Eu já vi código onde alguém implementou memoização global para um problema que chamava a sequência uma única vez. O resultado foi mais lento do que a versão iterativa simples porque o objeto cache crescia desnecessariamente. O formato padrão de memoização recursiva também tem um problema de stack overflow em linguagens que não fazem otimização de chamada de cauda. Em Python, por exemplo, o limite padrão de recursão é 1000 chamadas. Se você tentar calcular fib(1500) recursivamente, vai bater nesse limite antes mesmo do cálculo terminar.

a sequência de fibonacci e limites de precisão

Um problema que eu encontrei recentemente envolve o cálculo do 10000º termo da sequência em JavaScript. O número resultante excede em muito a capacidade do Number padrão, que tem precisão limitada a 2^53 - 1 para inteiros seguros. O resultado volta truncado e errado, sem nenhum aviso. A solução foi usar BigInt, que suporta inteiros arbitrariamente grandes. O código muda basicamente para adicionar o sufixo n nos literais:

function fibBig(n) {
  let a = 0n, b = 1n;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}
Uma observação importante: operações com BigInt são significativamente mais lentas do que com Number. Para n=100000, o cálculo com BigInt levou cerca de 2 segundos no meu ambiente, enquanto a versão com Number (antes de estourar a precisão) leva microssegundos. Se você está fazendo isso em um loop ou processando milhares de requisições, esse custo importa.

A propriedade de Pisano e quando ela realmente ajuda

Muita gente não sabe, mas a sequência de Fibonacci em módulo m é sempre periódica. Esse período é chamado de período de Pisano. Por exemplo, Fibonacci módulo 10 repete a cada 60 termos. Fibonacci módulo 100 repete a cada 300 termos. Isso parece abstrato até você precisar calcular fib(10^18) módulo 10^9+7. Fazer o loop até esse número é impossível. Com o período de Pisano, você reduz o expoente para um número muito menor e o cálculo fica viável. O período para módulo 10^9+7 é 2×10^9+16, o que ainda é grande, mas infinitamente melhor que 10^18.

O problema é que encontrar o período de Pisano para um módulo arbitrário não é trivial. Não existe uma fórmula fechada simples. A abordagem prática é fatorar o módulo em primos, encontrar o período para cada fator primo e depois calcular o mínimo múltiplo comum. Isso funciona bem para competições de programação, mas em produção real raramente vale a pena implementar a menos que você tenha um requisito específico de performance extrema.

Onde a abordagem iterativa falha e alternativas

Se você precisa do enésimo termo para valores de n acima de 10^7 em um contexto de servidor com restrições de memória apertadas, a iteração linear consome tempo demais. Nesse cenário, a multiplicação de matrizes com estratégia de exponenciação rápida reduz a complexidade para O(log n). A matriz básica é: [1 1]
[1 0]
Elevar essa matriz à potência n e ler o elemento superior esquerdo dá fib(n+1). O número de multiplicações de matriz é logarítmico, então para n=10^9 você faz cerca de 30 multiplicações no lugar de 10^9 iterações.

Porém, multiplicações de matriz têm uma constante maior. Para n abaixo de 10^6, a versão iterativa ainda é mais rápida na prática porque as operações são mais simples e melhor cacheadas. Eu usei essa otimização em um projeto onde precisávamos calcular termos na faixa de 10^12 e o ganho foi de minutos para frações de segundo.

Pegadinha comum: off-by-one e indices

Tem uma confusão persistente sobre se fib(0) é 0 ou 1. A convenção matemática padrão define fib(0)=0, fib(1)=1. Mas algumas bibliotecas e implementações antigas começam com fib(1)=1, fib(2)=1, o que desloca todos os índices em uma posição. Se você estiver integrando com código de outra equipe ou usando uma biblioteca legada, verifique isso antes. Um erro de índice aqui causa resultados incorretos silenciosamente, sem exception. Outro detalhe prático: a maioria das linguagens não tem uma função nativa de Fibonacci. No Python, scipy.special.fib existe, mas opera com arrays e é mais voltada para computação numérica do que para inteiros exatos. Para cálculo exato de termos grandes, escrever a sua própria função com BigInt ou recorrer a bibliotecas especializadas como gmpy2 é o caminho mais seguro.

Resumo rápido do que funciona em cenários reais

Termos pequenos (n < 1000): iterativo com Number, rápido e simples. Termos médios (n até 100000): iterativo com BigInt se precisar de precisão exata, senão Number com consciência do limite de precisão. Termos muito grandes (n acima de 10^9): multiplicação de matrizes com exponenciação rápida. Sempre verificar a convenção de indexação quando integrar com código externo. E evitar recursão pura sem memoização, exceto para fins educacionais ou debugging.