Algorithmes Python

Recursive Fibonacci with Memoization in Python

Plain recursive Fibonacci repeats the same work millions of times. Add a cache and it becomes instant.

Intermédiaire
2 min de lecture
1 exemple exécutable

Ce que vous allez apprendre

Writing Fibonacci recursively
Why the plain version is exponential
Memoization with functools.lru_cache

Exécuter dans le compilateur Python →

fib(4) without a cache

fib(4)
- fib(3)
  - fib(2)
  - fib(1)
- fib(2)computed again

With @lru_cache the second fib(2) is read from the cache. fib(10) = 55.

Remember answers you already computed

Calculer Fibonacci par récursivité est très court mais lent, car la même valeur est recalculée un très grand nombre de fois. La mémoïsation (memoization) consiste à garder en mémoire le résultat des appels précédents pour simplement le réutiliser ensuite, au lieu de tout recalculer.

Points clés

fib(n) = fib(n - 1) + fib(n - 2), with fib(0) = 0 and fib(1) = 1.
Without a cache, fib(3) is recomputed many times inside fib(10).
@lru_cache stores each result, so every fib(k) runs once: O(n).

Quand l’utiliser ?

Développer votre raisonnement et comprendre étape par étape le fonctionnement d’un algorithme.
Choisir la bonne approche quand il faut traiter beaucoup de données ou accélérer un programme.
Vous préparer aux examens, aux exercices et aux entretiens de programmation.

Voir comment ça marche

Appuyez sur Étape pour suivre chaque appel. Remarquez que fib recalcule sans cesse les mêmes petites valeurs, c'est pourquoi la version simple est lente.

Code d’exemple

Exécuter le code →

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))

Obtenir un bouton Run pour cet exemple

Résultat de l’exécution

Explication du code

Le décorateur @cache mémorise automatiquement le résultat de la fonction pour chaque valeur d'entrée. Une fois fibonacci(8) calculé, les appels suivants récupèrent directement le résultat. Le temps d'exécution passe ainsi d'exponentiel à O(n), en échange de O(n) mémoire pour stocker les résultats.

Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.

Exercices d’approfondissement

Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.

Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
Affichez l’état après chaque étape pour observer l’algorithme en action.
Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.

Exécuter dans le compilateur Python →

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis