Pour mesurer un algorithme qui s'appelle lui-même, on compte ses appels.
⏱️ Durée : environ 75 minutes · 🎓 Niveau : débutant · 🏅 Badge : Calculateur de profondeur
🎬 L'histoire
Kodi a écrit une fonction récursive pour calculer des suites de Fibonacci pour un bonus de fidélité. Pour n = 30, ça va. Pour n = 50, le serveur ne répond plus.
« Ta fonction recalcule les mêmes choses des milliards de fois, dit Sam. Dessine l'arbre de ses appels. »
Tu apprends à analyser le coût d'un algorithme récursif et à repérer les calculs répétés.
🎯 Ta mission
À la fin, je serai capable de :
- dessiner l'arbre des appels d'une fonction récursive
- compter le nombre d'appels
- écrire et résoudre une récurrence simple
- expliquer pourquoi Fibonacci naïf est exponentiel
- corriger avec la mémoïsation
🧩 Défi d'échauffement (5 XP)
Une rumeur démarre : chaque personne qui l'entend la répète à 2 autres personnes au tour suivant. Au tour 0, 1 personne la connaît. Combien de nouvelles personnes l'apprennent au tour 1, 2, 3, 10, 20 ? Que remarques-tu sur la vitesse de croissance ?
💡 Le concept
L'arbre des appels
Chaque appel récursif est un nœud ; ses appels internes sont ses enfants. Le coût total est lié au nombre de nœuds.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Pour fib(4) :
flowchart TD
A["fib(4)"] --> B["fib(3)"]
A --> C["fib(2)"]
B --> D["fib(2)"]
B --> E["fib(1)"]
C --> F["fib(1)"]
C --> G["fib(0)"]
D --> H["fib(1)"]
D --> I["fib(0)"]
Description du schéma : fib(4) appelle fib(3) et fib(2). fib(3) appelle à son tour fib(2) et fib(1). On voit que fib(2) est calculé deux fois : les mêmes calculs sont répétés.
Le nombre d'appels est environ 1,6ⁿ : exponentiel.
Les récurrences
Une récurrence décrit le coût d'un algorithme récursif en fonction du coût sur des problèmes plus petits.
| Algorithme | Récurrence | Résultat |
|---|---|---|
| Parcours récursif d'une liste (retire 1 élément) | T(n) = T(n−1) + 1 | O(n) |
| Recherche binaire | T(n) = T(n/2) + 1 | O(log n) |
| Tri fusion | T(n) = 2 T(n/2) + n | O(n log n) |
| Fibonacci naïf | T(n) = T(n−1) + T(n−2) + 1 | O(1,6ⁿ) |
Comment résoudre ?
Méthode de l'arbre :
- dessiner les niveaux de l'arbre des appels ;
- calculer le travail à chaque niveau ;
- additionner les niveaux.
Tri fusion : à chaque niveau, on traite n éléments au total ; il y a log₂ n niveaux ; donc n log n.
La mémoïsation
Si les mêmes sous-problèmes reviennent, on mémorise leurs résultats dans un dictionnaire.
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n < 2:
return n
if n not in memo:
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
Chaque valeur n'est calculée qu'une fois : O(n). On a échangé de la mémoire contre du temps.
🔍 Exemple pas à pas
Problème : mesurer le nombre d'appels de fib et de fib_memo.
appels = 0
def fib(n):
global appels
appels += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
for n in (10, 15, 20, 25):
appels = 0
fib(n)
print(n, appels)
# 10 177
# 15 1973
# 20 21891
# 25 242785
Observation : quand n augmente de 5, le nombre d'appels est multiplié par environ 11 : croissance exponentielle.
def fib_memo(n, memo=None, compteur=None):
if memo is None:
memo, compteur = {}, [0]
compteur[0] += 1
if n < 2:
return n
if n not in memo:
memo[n] = fib_memo(n - 1, memo, compteur) + fib_memo(n - 2, memo, compteur)
return memo[n]
def appels_memo(n):
memo, compteur = {}, [0]
fib_memo(n, memo, compteur)
return compteur[0]
print([appels_memo(n) for n in (10, 15, 20, 25)]) # [19, 29, 39, 49]
Avec mémoïsation : environ 2n appels. Pour n = 25 : 49 appels contre 242 785.
✍️ À toi, avec aide (10 XP)
Voici une fonction récursive :
def somme(liste):
if not liste:
return 0
return liste[0] + somme(liste[1:])
- Écris la récurrence du nombre d'appels T(n).
- Quel est le nombre d'appels pour n = 5 ?
- Remarque cachée :
liste[1:]copie la liste. Quel est le coût total, copies incluses ?
💡 Indice 1
Chaque appel en fait un autre sur une liste plus courte de 1.
💡 Indice 2
T(0) = 1, T(n) = 1 + T(n−1).
💡 Indice 3
La copie à l'étape k coûte environ n−k éléments.
✅ Réponse
- T(n) = T(n−1) + 1, donc T(n) = n + 1 appels.
- n = 5 : 6 appels (dont l'appel sur la liste vide).
- Les copies coûtent (n−1) + (n−2) + … + 1 ≈ n²/2 : le coût total est O(n²), alors qu'une boucle simple est O(n). La récursion n'est donc pas gratuite.
🚀 À toi, en solo (20 XP)
Compte le nombre d'appels pour calculer le nombre de chemins dans une grille n × n, en ne bougeant que vers la droite ou le bas :
def chemins(i, j):
if i == 0 or j == 0:
return 1
return chemins(i - 1, j) + chemins(i, j - 1)
- Mesure le nombre d'appels pour
chemins(n, n)avec n = 4, 6, 8, 10. - Ajoute la mémoïsation (dictionnaire indexé par
(i, j)) et compare. - Quel est le Big O avec mémoïsation ?
✅ Pistes de correction
appels = 0
def chemins(i, j):
global appels
appels += 1
if i == 0 or j == 0:
return 1
return chemins(i - 1, j) + chemins(i, j - 1)
def chemins_memo(i, j, memo, compteur):
compteur[0] += 1
if i == 0 or j == 0:
return 1
if (i, j) not in memo:
memo[(i, j)] = chemins_memo(i - 1, j, memo, compteur) + chemins_memo(i, j - 1, memo, compteur)
return memo[(i, j)]
for n in (4, 6, 8, 10):
appels = 0
r = chemins(n, n)
c = [0]
assert chemins_memo(n, n, {}, c) == r
print(n, r, appels, c[0])
Sans mémoïsation, le nombre d'appels est de l'ordre du résultat lui-même (très grand). Avec mémoïsation : O(n²) cases, chacune calculée une fois.
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Sous-problèmes répétés | Coût exponentiel caché | Dessiner l'arbre des appels, mémoïser si besoin |
| Copier à chaque appel | liste[1:] rend O(n²) | Passer des indices au lieu de copier |
| Mémo partagé par erreur | Argument par défaut memo={} conservé entre appels | Créer le dictionnaire dans la fonction |
| Profondeur de récursion | RecursionError pour n grand | Utiliser une boucle ou augmenter la limite avec prudence |
🐉 Mini-boss (40 XP)
Rendre la monnaie (nombre minimal de pièces). Pièces [1, 3, 4], montant 6 : la réponse optimale est 2 (3 + 3).
- Écris la version récursive naïve
min_pieces(montant): essaie chaque pièce. - Compte les appels pour montant = 10, 15, 20, 25.
- Ajoute la mémoïsation et compte à nouveau.
- Écris la récurrence et le Big O avec et sans mémoïsation.
✅ Pistes de correction
appels = 0
def min_pieces(m, pieces=(1, 3, 4)):
global appels
appels += 1
if m == 0:
return 0
meilleur = float("inf")
for p in pieces:
if p <= m:
meilleur = min(meilleur, 1 + min_pieces(m - p, pieces))
return meilleur
def min_pieces_memo(m, memo, compteur, pieces=(1, 3, 4)):
compteur[0] += 1
if m == 0:
return 0
if m not in memo:
meilleur = float("inf")
for p in pieces:
if p <= m:
meilleur = min(meilleur, 1 + min_pieces_memo(m - p, memo, compteur, pieces))
memo[m] = meilleur
return memo[m]
for m (, , ):
appels =
r = min_pieces(m)
c = []
min_pieces_memo(m, {}, c) == r
(m, r, appels, c[])
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Pourquoi fib(n) naïf est-il très lent ?
- A. il recalcule les mêmes sous-problèmes
- B. il utilise trop de variables
- C. il est écrit en Python
2. La mémoïsation consiste à :
- A. effacer la mémoire
- B. mémoriser les résultats déjà calculés
- C. supprimer la récursion
3. La récurrence T(n) = T(n/2) + 1 correspond à :
- A. le tri fusion
- B. Fibonacci
- C. la recherche binaire
4. 🔁 Révision mission 03 : Deux boucles imbriquées de n tours donnent :
- A. O(n²)
- B. O(2n)
- C. O(n)
5. 🔁 Révision mission 02 : O(n log n) est :
- A. plus rapide que O(n)
- B. plus lent que O(n) et plus rapide que O(n²)
- C. identique à O(n²)
✅ Réponses
- A.
- B.
- C.
- A.
- B.
🪞 Je réfléchis (10 XP)
- As-tu déjà refait plusieurs fois un même calcul sans t'en rendre compte ? Dans quel contexte ?
- Quel est l'avantage d'un schéma des appels par rapport à une formule seule ?
🎒 À retenir
- L'arbre des appels montre le travail total.
- Une récurrence exprime le coût d'un algorithme récursif.
- Sous-problèmes répétés → coût exponentiel.
- La mémoïsation transforme l'exponentiel en polynomial.
- La récursion a aussi un coût caché (copies, pile).
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Calculateur de profondeur
← Mission 03 — Boucles et compositions · Mission 05 — Le coût des structures de données →
HEF-030 — Complexité

