Le miroir dans le miroir
Mets deux miroirs face à face. Tu vois ton image dans l’image, encore et encore, sans fin.
Une fonction récursive mal écrite fait la même chose : elle s’appelle sans jamais s’arrêter. Heureusement, Python finit par dire stop. Apprenons à lire ce stop et à réparer.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Cas de base | Le cas simple qui arrête les appels. | if n == 0: |
| Récursion infinie | Des appels qui ne s’arrêtent jamais, car le cas de base n’arrive pas. | f(n + 1) |
| Profondeur | Le nombre d’appels empilés en même temps. | 500 appels |
| RecursionError | L’erreur de Python quand la pile est trop haute. | maximum recursion depth exceeded |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Trois défauts classiques
Premier défaut : pas de cas de base. Les appels ne s’arrêtent jamais.
Deuxième défaut : l’appel ne rapproche pas du cas de base. Par exemple f(n + 1) quand on veut arriver à 0.
Troisième défaut : l’appel garde le même problème, comme f(mot) au lieu de f(mot[1:]).
À toi : jusqu’où peut-on descendre ?
def descendre(n):
if n == 0:
return 0
return 1 + descendre(n - 1)
print(descendre(10))
print(descendre(500))
# Change 500 en 5000 et relance.
# Lis le message d'erreur : Python s'arrête de lui-même.
# Il refuse d'empiler plus d'environ mille appels.
Quel est le défaut ?
À toi de jouer
Quel est le défaut ?
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
Exemple travaillé : une pile qui monte
| Appel | Valeur de n | Cas de base atteint ? |
|---|---|---|
| f(3) | 3 | non, on rappelle f(4) |
| f(4) | 4 | non, on rappelle f(5) |
| f(5) | 5 | non, on rappelle f(6) |
| f(6) | 6 | non, et ainsi de suite jusqu’à l’erreur |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Le calcul refait dix fois
Autre piège : une fonction peut être correcte, et pourtant très lente.
Prends la suite de Fibonacci : chaque nombre est la somme des deux précédents. 0, 1, 1, 2, 3, 5, 8, 13.
Écrite en récursif, la fonction refait les mêmes calculs encore et encore.
À toi : compter les appels
compteur = 0
def fibo(n):
global compteur
compteur = compteur + 1
if n < 2:
return n
return fibo(n - 1) + fibo(n - 2)
for n in [2, 3, 4, 5, 10, 20]:
compteur = 0
resultat = fibo(n)
print("fibo(", n, ") =", resultat, "avec", compteur, "appels")
# Les appels grandissent beaucoup plus vite que n.
Exemple travaillé : le nombre d’appels de fibo
| n | fibo(n) | Nombre d’appels |
|---|---|---|
| 2 | 1 | 3 |
| 3 | 2 | 5 |
| 4 | 3 | 9 |
| 5 | 5 | 15 |
| 10 | 55 | 177 |
| 20 | 6765 | 21891 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.