La suite de Fibonacci écrite récursivement recalcule sans cesse les…

def fibo_naif(n):
    if n < 2:
        return n
    return fibo_naif(n - 1) + fibo_naif(n - 2)


def fibo_memo(n, memoire=None):
    """Fibonacci avec memoire des resultats deja calcules."""
    if memoire is None:
        memoire = {}
    if n < 2:
        return n
    if n in memoire:
        return memoire[n]
    memoire[n] = fibo_memo(n - 1, memoire) + fibo_memo(n - 2, memoire)
    return memoire[n]

Les mesures. Pour $F(25)=75025$ : $242785$ appels sans mémoire, $49$ avec — un rapport de près de cinq mille. En temps, sur $F(28)$ : $0,022$ s contre $0,000006$ s, soit un facteur $3600$. Et l'écart grandit avec $n$ : la version naïve double son travail à chaque unité, la version mémoïsée l'augmente d'un appel. fibo_memo(90) rend instantanément $2880067194370816120$, quand la version naïve demanderait des milliers d'années.

Pourquoi memoire=None et non memoire={}. Une valeur par défaut n'est évaluée qu'une fois, à la définition de la fonction : le dictionnaire serait partagé par tous les appels, y compris ceux de programmes différents. Ici, ce partage donnerait par chance le bon résultat — mais sur une fonction dont les résultats dépendent d'autre chose que n, il donnerait des réponses fausses, tirées d'un calcul antérieur. C'est le même piège que dict.fromkeys(cles, []) : une seule structure là où l'on en croyait plusieurs.

Ce que l'exercice montre du chapitre. Le dictionnaire ne sert pas seulement à ranger des données : il sert à ne pas refaire un calcul. C'est l'un des usages les plus courants en pratique, et il repose entièrement sur la propriété du chapitre — retrouver une valeur par sa clé sans parcourir quoi que ce soit.