Une fonction qui s’appelle elle-même
Une fonction récursive est une fonction qui s’appelle elle-même sur un problème plus petit. La récursivité remplace parfois une boucle compliquée par deux règles courtes, et elle sert pour les arbres, les tris et les parcours de graphes.
Pour calculer la somme d’un panier de dix articles, on peut dire : le prix du premier article plus la somme des neuf autres. Cette phrase contient déjà la récursion.
À la fin de cette leçon
Remarque
Je peux écrire une fonction récursive avec un cas de base.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Récursivité | une fonction qui s’appelle elle-même | |
| Cas de base | le cas le plus simple, résolu sans nouvel appel | une liste vide |
| Cas récursif | le cas où la fonction s’appelle sur un problème plus petit | |
| Pile d’appels | les appels en cours, rangés les uns sur les autres | |
| Factorielle | le produit des entiers de 1 à n | 4 × 3 × 2 × 1 = 24 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une fonction récursive a deux parties
Une fonction récursive a toujours deux parties. Le cas de base est le cas le plus simple : la fonction rend la réponse sans nouvel appel.
Le cas récursif appelle la fonction sur un problème plus petit. Chaque appel doit se rapprocher du cas de base, sinon la fonction ne s’arrête jamais.
La factorielle, en deux règles
def factorielle(n):
if n <= 1:
return 1 # cas de base : on s’arrête
return n * factorielle(n - 1) # cas récursif : un problème plus petit
print(factorielle(5))
# Remplacez 5 par 10 : vous attendez 3628800.
Exemple travaillé : factorielle(3)
| Appel | Ce qu’il attend | Ce qu’il rend |
|---|---|---|
| factorielle(3) | 3 × factorielle(2) | 6 |
| factorielle(2) | 2 × factorielle(1) | 2 |
| factorielle(1) | rien : c’est le cas de base | 1 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La pile d’appels garde les appels en attente
Quand factorielle(3) appelle factorielle(2), elle attend le résultat. L’appel en attente reste dans la pile d’appels.
La pile grandit jusqu’au cas de base, puis les résultats remontent un à un. Python limite la pile à environ 1 000 appels emboîtés : au-delà, il lève l’erreur RecursionError.
Erreur fréquente
Attention
Beaucoup pensent qu’une fonction récursive finit toujours toute seule. Sans cas de base, ou si l’appel ne se rapproche pas de lui, elle s’appelle sans fin jusqu’à l’erreur de profondeur. Vérifiez deux choses : le cas de base existe, et chaque appel s’en rapproche.
La factorielle de dix
python3 -c "exec('def fact(n):\n if n <= 1:\n return 1\n return n * fact(n - 1)\nprint(fact(10))')"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.
Une récursion sans cas de base
python3 -c "exec('def f(n):\n return f(n + 1)\nf(0)')" 2>&1 | tail -1Affiché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.
Deux appels récursifs peuvent exploser
Dans la suite de Fibonacci, chaque nombre est la somme des deux précédents : 0, 1, 1, 2, 3, 5, 8, 13. Les cas de base sont 0 et 1.
La fonction s’appelle ici deux fois, et chacun de ces appels s’appelle deux fois à son tour. Le nombre d’appels grandit très vite.
Fibonacci qui compte ses appels
# Chaque nombre est la somme des deux précédents.
appels = 0
def fibonacci(n):
global appels
appels = appels + 1
if n < 2:
return n # cas de base : fibonacci(0) = 0 et fibonacci(1) = 1
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(10), "en", appels, "appels")
# Mettez 15 : combien d’appels pour un seul résultat ?
Les appels de fibonacci(n)
| n | Résultat | Nombre d’appels |
|---|---|---|
| 10 | 55 | 177 |
| 20 | 6 765 | 21 891 |
| 30 | 832 040 | 2 692 537 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Compter les appels de fibonacci(10)
python3 -c "exec('compteur = 0\ndef fib(n):\n global compteur\n compteur = compteur + 1\n if n < 2:\n return n\n return fib(n - 1) + fib(n - 2)\nfib(10)\nprint(compteur)')"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.
Le tri par fusion, enfin en code
def fusionner(a, b):
resultat = []
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
resultat.append(a[i])
i = i + 1
else:
resultat.append(b[j])
j = j + 1
return resultat + a[i:] + b[j:]
def tri_fusion(liste):
if len(liste) <= 1:
return liste # une seule valeur est déjà triée
milieu = len(liste) // 2
gauche = tri_fusion(liste[:milieu])
droite = tri_fusion(liste[milieu:])
return fusionner(gauche, droite)
print(tri_fusion([29, 10, 14, 37, 13]))