Mesurer le chevauchement

def fib_compte(n, compteur):
    compteur[0] += 1
    if n <= 1:
        return n
    return fib_compte(n - 1, compteur) + fib_compte(n - 2, compteur)

• Nombres d'appels mesurés :
• Pour $n=10$ : version naïve $=177$ appels, version mémoïsée $=19$ appels.
• Pour $n=20$ : version naïve $=21891$ appels, version mémoïsée $=39$ appels.
• Pour $n=30$ : version naïve $=2692537$ appels, version mémoïsée $=59$ appels.
• Lois de croissance : La version naïve suit une croissance exponentielle proportionnelle à ${\Phi }^n$ (où $\Phi \approx 1,618$ est le nombre d'or). La version mémoïsée présente une croissance linéaire valant exactement $2n-1$ appels. Pour $n=30$, l'approche mémoïsée est environ $45000$ fois plus rapide.