Algoritmos em Python

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.

  • Intermediário
  • 2 min de leitura
  • 1 exemplo executável

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ó.

Do caderno ao código
@cache📓 Mantenha um caderno de respostas
fibonacci(number - 1) + fibonacci(number - 2)🧮 Resolva usando duas perguntas menores
if number < 2: return number🛑 As duas primeiras respostas são conhecidas
fibonacci(10)⚡ Cada resposta menor é calculada uma vez: rápido
Guarde cada resultado na primeira vez; reutilize depois.
Em uma frase

A 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

  1. if number < 2: return number dá os dois primeiros termos, 0 e 1.
  2. fibonacci(number - 1) + fibonacci(number - 2) segue a definição diretamente.
  3. @cache, de functools, lembra cada resultado, então cada fibonacci(k) roda uma vez só.
  4. 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

Executar código →
main.py
from functools import cache

@cache
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

print(fibonacci(10))
Gerar um botão Run para este exemplo

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.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Recursão sem cache

Os mesmos valores são recalculados de novo e de novo, e fib(40) leva muitos segundos.

Problema
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)
Correção
@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.

Todos os desafios