Les poupées russes et les fonctions
La récursivité est une méthode où une fonction s’appelle elle-même pour résoudre un problème plus petit. Elle écrit en quelques lignes des solutions qui seraient longues avec des boucles.
Pense aux poupées russes : ouvrir la grande poupée te donne une poupée un peu plus petite, qu’il faut ouvrir de la même façon.
À la fin de cette leçon
Remarque
Je peux écrire une fonction qui s’appelle elle-même et qui s’arrête.
Mots clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Récursivité | une fonction qui s’appelle elle-même | |
| Appel récursif | la ligne où la fonction s’appelle, avec un problème plus petit | |
| Cas de base | le cas si simple qu’on répond sans nouvel appel | |
| Pile d’appels | la pile où Python garde les appels qui attendent une réponse | |
| Limite de récursion | le nombre maximal d’appels qui attendent en même temps | |
| Débordement de pile | l’erreur quand la limite est dépassée | RecursionError |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une fonction récursive a deux parties
Un cas de base : le cas le plus simple, qui donne la réponse sans appeler la fonction. Sans lui, la fonction ne s’arrête jamais.
Un appel récursif : la fonction s’appelle avec un problème plus petit. Chaque appel doit se rapprocher du cas de base.
Lance un compte à rebours récursif
def compte_a_rebours(n):
if n == 0: # cas de base
print("Partez !")
return
print(n)
compte_a_rebours(n - 1) # appel récursif, plus petit
compte_a_rebours(3)
# Change 3 en 5. Combien de lignes s'affichent ?
Additionner de 1 à n par récursivité
Pour additionner de 1 à 3, on peut dire : 3 plus la somme de 1 à 2. Et la somme de 1 à 2 est 2 plus la somme de 1 à 1. On finit par la somme de 1 à 0, qui vaut 0.
Ce 0 est le cas de base. Il arrête les appels, puis les réponses remontent une à une.
Exemple travaillé : que fait somme(3) ?
| Appel | Ce qu’il calcule | Valeur rendue |
|---|---|---|
| somme(3) | 3 + somme(2) | attend… |
| somme(2) | 2 + somme(1) | attend… |
| somme(1) | 1 + somme(0) | attend… |
| somme(0) | cas de base | 0 |
| Les réponses remontent | somme(1) rend 1, somme(2) rend 3, somme(3) rend 6 | 6 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Lance la somme récursive
def somme(n):
if n == 0:
return 0 # cas de base
return n + somme(n - 1) # appel récursif
print(somme(3))
print(somme(10))
# Calcule somme(100) : c'est 5050.
Python garde les appels dans une pile
Quand somme(3) appelle somme(2), il attend la réponse. Python note cet appel en attente sur une pile d’appels, comme une pile d’assiettes.
Le dernier appel arrivé répond en premier. Cette pile a une taille limitée : si les appels sont trop nombreux, Python s’arrête avec une erreur.
Regarde les appels de puissance
def puissance(a, n):
print("appel avec n =", n)
if n == 0:
return 1 # cas de base
return a * puissance(a, n - 1)
print(puissance(2, 3))
# Combien d'appels pour puissance(2, 3) ? Compte les lignes.
Lis la limite de récursion de Python
docker exec jupyter python3 -c "import sys; print(sys.getrecursionlimit())"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Vérifie deux résultats à la main
docker exec jupyter python3 -c "print(sum(range(1, 6)), 2 ** 5)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Ce que disent les deux Runs
Le premier Run affiche 1000. Python accepte au plus environ mille appels en attente en même temps. Au-delà, il lève une erreur RecursionError.
Le second Run affiche 15 32. La somme de 1 à 5 vaut 15 et 2 puissance 5 vaut 32. Tu peux comparer avec ce que rendent somme(5) et puissance(2, 5).
Une erreur fréquente
Attention
Beaucoup oublient le cas de base, ou écrivent un appel qui ne rapproche pas du cas de base. La fonction s’appelle alors sans fin. Python s’arrête avec une RecursionError. Avant d’écrire l’appel, demande-toi : quel est le cas le plus simple, et comment chaque appel s’en approche-t-il ?
Pour aller plus loin : la factorielle
La factorielle de 4, notée 4!, vaut 4 × 3 × 2 × 1, soit 24. Celle de 0 vaut 1.
Écris factorielle(n) récursive. Quel est son cas de base ? Quel appel plus petit utilise-t-elle ?