Algoritmi Python

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.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dal quaderno al codice
@cache📓 Tieni un quaderno di risposte
fibonacci(number - 1) + fibonacci(number - 2)🧮 Risolvi usando due domande più piccole
if number < 2: return number🛑 Le prime due risposte sono note
fibonacci(10)⚡ Ogni risposta più piccola viene calcolata una volta: veloce
Salva ogni risultato la prima volta, poi riusalo.
In una frase

La 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

  1. if number < 2: return number dà i primi due termini, 0 e 1.
  2. fibonacci(number - 1) + fibonacci(number - 2) segue direttamente la definizione.
  3. @cache di functools ricorda ogni risultato, quindi ogni fibonacci(k) viene eseguito una volta sola.
  4. Senza @cache, fibonacci(10) farebbe 177 chiamate, con @cache solo 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

Esegui codice →
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))
Crea un pulsante Run per questo esempio

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.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Ricorsione senza cache

Gli stessi valori vengono ricalcolati di continuo, e fib(40) impiega parecchi secondi.

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

Tutte le sfide