Fibonacci recursivo com memoization
Memoization guarda resultados já calculados.
O que é Fibonacci recursivo com memoization?
Memoization guarda resultados já calculados.
Evite recalcular os mesmos termos.
Quando usar?
- Entender algoritmos e estruturas de dados.
- Observar cada etapa e tratar casos de borda.
- Comparar tempo de execução e memória.
Código de exemplo
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))Saída esperada
55Como funciona
O cache reduz o tempo exponencial ingênuo para O(n), com memória O(n).
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Altere as entradas e teste casos de borda antes de usar conjuntos de dados maiores.
- Teste entrada vazia, um elemento e duplicados.
- Mostre o estado após cada etapa.
- Compare o desempenho com outra solução.