Fibonacci con ricorsione e memoizzazione in Python
In questa lezione calcolerai i numeri di Fibonacci con la ricorsione e userai la memoizzazione per non ricalcolare risultati già noti.
Introduzione
Il problema
La definizione ricorsiva di Fibonacci è bellissima ma lentissima: calcolare il quarantesimo termine ripete gli stessi calcoli più piccoli centinaia di milioni di volte. La memoizzazione risolve il problema con una riga e ti insegna un'idea chiave della programmazione dinamica.
Immaginalo così
La memoizzazione è come uno studente che scrive ogni risposta su un quaderno. Quando gli chiedono di nuovo fib(5), non rifà i conti: legge la risposta sul quaderno. Ogni domanda viene risolta una volta sola.
@cache📓 Tieni un quaderno di rispostefibonacci(number - 1) + fibonacci(number - 2)🧮 Risolvi usando due domande più piccoleif number < 2: return number🛑 Le prime due risposte sono notefibonacci(10)⚡ Ogni risposta più piccola viene calcolata una volta: veloceLa memoizzazione salva il risultato di ogni chiamata di funzione in base ai suoi argomenti, così le chiamate ripetute restituiscono il risultato salvato invece di ricalcolarlo.
Punti chiave
if number < 2: return numberdà i primi due termini, 0 e 1.fibonacci(number - 1) + fibonacci(number - 2)segue direttamente la definizione.@cachedifunctoolsricorda ogni risultato, quindi ognifibonacci(k)viene eseguito una volta sola.- Senza
@cache,fibonacci(10)farebbe 177 chiamate, con@cachesolo 11.
Quando si usa?
- Funzioni ricorsive che ripetono gli stessi sottoproblemi: percorsi in una griglia, dare il resto con le monete, spezzare un testo in parole.
- Imparare l'idea dietro la programmazione dinamica.
- Accelerare qualsiasi funzione pura chiamata spesso con gli stessi argomenti.
Quando non serve
- Funzioni con effetti collaterali o con risultati che cambiano nel tempo: la cache restituirebbe risposte non più valide.
- Ricorsione molto profonda: anche con una cache,
fib(5000)può superare il limite di ricorsione. Un ciclo evita il problema.
Guarda come funziona
Premi Passo per seguire ogni chiamata. Nota come fib ricalcola più volte gli stessi valori piccoli, ed è per questo che la versione semplice è lenta.
Codice di esempio
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))
Risultato dell'esecuzione
55
Spiegazione del codice
Il decoratore @cache memorizza automaticamente il risultato della funzione per ogni valore in ingresso. Una volta calcolato fibonacci(8), le chiamate successive prendono semplicemente il risultato pronto. Così il tempo di esecuzione scende da esponenziale a O(n), in cambio di O(n) di memoria per salvare i risultati.
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Ricorsione senza cache
Gli stessi valori vengono ricalcolati di continuo, e fib(40) impiega parecchi secondi.
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)
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- Numero di Fibonacci Restituisci l'n-esimo numero di Fibonacci. Facile
- Conta le Sequenze di Dadi Conta le sequenze ordinate di lanci di dado con una somma data. Media