Complétez de mémoire, puis vérifiez avec la page de corrigé.
Une poupée russe contient une poupée plus petite, qui en contient une autre, jusqu'à la plus petite. Une fonction récursive fonctionne de la même façon : elle s'appelle elle-même sur un problème plus petit, jusqu'à un cas simple qu'elle sait résoudre directement.
Principe
Définition — fonction récursive :
Définition — cas de base :
Règle
La pile d'appels
Règle
Quand l'utiliser
Règle
Exemple
Écris une fonction récursive somme(n) = 1 + 2 + … + n.
6.
7.
8.
Résultat :
Piège
Oublier le cas de base.
Écrire le cas de base en premier.
Écrire une fonction récursive
10.
11.
12.
13.
Ai-je défini le vocabulaire ?
Mon code est-il testé sur un exemple ?
Ai-je traité les cas limites ?
Ai-je justifié la complexité ou le résultat ?
Corrigé · à détacher
La récursivité
1.Fonction qui s'appelle elle-même dans sa définition.
2.Cas simple résolu sans appel récursif ; il garantit que la fonction s'arrête.
3.Exemple : def fact(n): return 1 if n == 0 else n * fact(n - 1).
4.Chaque appel est mis en attente sur la pile d'appels jusqu'à ce que l'appel suivant renvoie son résultat. Sans cas de base, ou si les appels ne s'en rapprochent pas, la pile déborde : Python lève une RecursionError (limite de l'ordre de 1 000 appels par défaut).
5.La récursivité est naturelle pour les structures elles-mêmes récursives (arbres, listes chaînées) et pour les algorithmes diviser pour régner (tri fusion, exponentiation rapide). Certains calculs récursifs naïfs recalculent les mêmes valeurs (Fibonacci) : la mémoïsation ou la programmation dynamique les accélèrent.
6.Cas de base : if n == 0: return 0.
7.Appel récursif : return n + somme(n - 1).
8.Vérifier : somme(3) = 3 + 2 + 1 + 0 = 6.
9.Une fonction récursive combine un cas de base et un appel sur un problème plus petit.
10.Identifier le cas de base et sa valeur.
11.Exprimer le problème à l'aide du même problème plus petit.
12.Vérifier que chaque appel se rapproche du cas de base.