Fibonacci com Memoização
Armazena resultados já calculados para evitar recálculos exponenciais — de O(2ⁿ) para O(n) com uma simples tabela.
O(n)O(n)Como Funciona
Passo a passo do algoritmo
O problema da recursão simples
A implementação recursiva ingênua de fib(n) chama fib(n-1) e fib(n-2), cada uma chamando mais dois, resultando em uma árvore de chamadas com 2ⁿ nós. Para fib(40), isso é mais de um trilhão de chamadas.
fib(n) = fib(n-1) + fib(n-2) → O(2ⁿ) chamadasMemoizar o resultado
Criamos um array memo[] inicializado com null. Assim que calculamos fib(k), armazenamos o resultado em memo[k]. Nas próximas vezes que fib(k) for solicitado, retornamos memo[k] diretamente.
memo = [null, null, ..., null] // tamanho n+1Verificar cache antes de calcular
No início de cada chamada fib(k), verificamos se memo[k] não é null. Se já tiver valor, retornamos imediatamente sem nenhum cálculo adicional. Esse é o "cache hit".
se memo[k] ≠ null: retornar memo[k] // cache hit!A economia exponencial
Com memoização, cada fib(k) é calculado exatamente uma vez. fib(40) passa de ~2⁴⁰ chamadas para apenas 40 chamadas únicas — uma redução de mais de um trilhão de vezes.
sem memo: O(2ⁿ) → com memo: O(n) tempo, O(n) espaçoCasos base
fib(0)=0 e fib(1)=1 são os casos base que inicializam a recursão. Ao atingirmos esses valores, simplesmente os armazenamos em memo e retornamos sem mais chamadas recursivas.
se k ≤ 1: memo[k] = k; retornar kImplementação
Código comentado em JavaScript e Python
function fibonacci(n, memo = {}) {
// Verificar cache
if (n in memo) return memo[n];
// Casos base
if (n <= 1) return n;
// Calcular e memoizar
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
// Versão com array
function fibArray(n) {
const memo = new Array(n + 1).fill(null);
memo[0] = 0;
memo[1] = 1;
function fib(k) {
if (memo[k] !== null) return memo[k]; // cache hit!
memo[k] = fib(k - 1) + fib(k - 2);
return memo[k];
}
return fib(n);
}
// Exemplos
console.log(fibonacci(10)); // 55
console.log(fibonacci(40)); // 102334155 (instantâneo!)
console.log(fibonacci(50)); // 12586269025Playground
Visualize o algoritmo em ação
Quando Usar
Cenários ideais para este algoritmo
Introdução à PD
Fibonacci é o exemplo didático clássico de como identificar subproblemas sobrepostos e aplicar memoização.
Otimização de recursão
O padrão se aplica a qualquer função recursiva com subproblemas repetidos: calcule uma vez, reutilize sempre.
Contagem de caminhos
Contar caminhos em grids, escadas ou grafos — estrutura idêntica à de Fibonacci com memoização.
Compiladores e parsers
Memoização é amplamente usada em parsers de descida recursiva para evitar recomputar derivações já analisadas.
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Sem memoização | O(2ⁿ) |
| Com memoização (top-down) | O(n) |
| Bottom-up (tabulação) | O(n) |