Fibonacci com recursão e memoização em Python
Nesta lição, você vai calcular números de Fibonacci com recursão e usar memoização para não recalcular resultados já conhecidos.
Introdução
O problema
A definição recursiva de Fibonacci é bonita, mas extremamente lenta: calcular o 40º termo repete os mesmos cálculos menores centenas de milhões de vezes. A memoização resolve isso com uma linha e ensina uma ideia central da programação dinâmica.
Pense assim
A memoização é como um aluno que anota cada resposta em um caderno. Quando perguntam fib(5) de novo, ele não refaz o trabalho; lê a resposta no caderno. Cada pergunta é resolvida uma vez só.
@cache📓 Mantenha um caderno de respostasfibonacci(number - 1) + fibonacci(number - 2)🧮 Resolva usando duas perguntas menoresif number < 2: return number🛑 As duas primeiras respostas são conhecidasfibonacci(10)⚡ Cada resposta menor é calculada uma vez: rápidoA memoização guarda o resultado de cada chamada de função pelos seus argumentos, então chamadas repetidas devolvem o resultado guardado em vez de recalculá-lo.
Pontos-chave
if number < 2: return numberdá os dois primeiros termos, 0 e 1.fibonacci(number - 1) + fibonacci(number - 2)segue a definição diretamente.@cache, defunctools, lembra cada resultado, então cadafibonacci(k)roda uma vez só.- Sem
@cache,fibonacci(10)faria 177 chamadas; com ele, 11.
Quando usar?
- Funções recursivas que repetem os mesmos subproblemas: caminhos em uma grade, troco de moedas, divisão de palavras.
- Aprender a ideia por trás da programação dinâmica.
- Acelerar qualquer função pura chamada muitas vezes com os mesmos argumentos.
Quando não é preciso
- Funções com efeitos colaterais ou resultados que mudam com o tempo: o cache devolveria respostas desatualizadas.
- Recursão muito profunda: mesmo com cache,
fib(5000)pode passar do limite de recursão; um laço evita isso.
Veja como funciona
Clique em Passo para seguir cada chamada. Repare como fib calcula os mesmos valores pequenos várias vezes; por isso a versão simples é lenta.
Código de exemplo
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))
Resultado da execução
55
Explicação do código
O decorador @cache memoriza automaticamente o resultado da função para cada valor de entrada. Depois que fibonacci(8) é calculado uma vez, as próximas chamadas apenas pegam o resultado pronto. Com isso, o tempo de execução cai de exponencial para O(n), em troca de O(n) de memória para guardar os resultados.
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Recursão sem cache
Os mesmos valores são recalculados de novo e de novo, e fib(40) leva muitos segundos.
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
Terminou esta lição?
Marque como aprendida para acompanhar seu progresso.
Pratique com um desafio
Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.
- Número de Fibonacci Retorne o n-ésimo número de Fibonacci. Fácil
- Contar Sequências de Dados Conte sequências ordenadas de lançamentos de dado com um total específico. Médio