Fibonacci ricorsivo con memoization
La memoization conserva i risultati già calcolati.
Che cos’è Fibonacci ricorsivo con memoization?
La memoization conserva i risultati già calcolati.
Evita di ricalcolare gli stessi termini.
Quando si usa?
- Comprendere algoritmi e strutture dati.
- Osservare ogni passaggio e gestire i casi limite.
- Confrontare tempo di esecuzione e memoria.
Codice di esempio
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))Output previsto
55Come funziona
La cache riduce il tempo esponenziale ingenuo a O(n), con memoria O(n).
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi pratici
Modifica gli input e verifica i casi limite prima di usare dataset più grandi.
- Prova input vuoto, un elemento e duplicati.
- Stampa lo stato dopo ogni passaggio.
- Confronta le prestazioni con un’altra soluzione.