Récursivité
Une fonction qui s'appelle elle-même
- La récursion est quand une fonction s'appelle elle-même.
- Chaque appel devrait travailler sur une version plus petite du problème.
- Bien résolu, le problème se réduit jusqu'à devenir trivial à résoudre.
Cas de base et cas récursif
- Le cas de base est le cas le plus simple — il arrête la récursion.
- Le cas récursif appelle la fonction à nouveau avec une entrée plus petite.
- Sans un cas de base, la fonction ne s'arrête jamais (une erreur).
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
Un exemple détaillé : factorielle
- La factorielle
n!signifien × (n-1) × ... × 1. - Sous forme récursive :
n! = n × (n-1)!, et le cas de base est0! = 1. - Chaque appel multiplie
npar la factorielle de l'inférieur d'une unité.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
Comment l'ordinateur l'exécute
- Chaque appel est mis en attente sur une pile d'appels pendant qu'il attend l'appel interne.
- Quand le cas de base retourne, les appels en attente se terminent un par un.
- Trop d'appels déborde la pile — Python lève une
RecursionError.
En pseudocode Cambridge
- Une fonction récursive nomme clairement son cas de base et son cas récursif.
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
Erreurs courantes
- Toute récursion a besoin d'un cas de base, sinon elle déborde la pile d'appels.
- Chaque appel doit se rapprocher du cas de base.
À vous maintenant
- Donnez à chaque fonction un cas de base et un cas récursif.
- Appuyez sur Vérifier la réponse pour tester votre code.
La récursion revient des feuilles
Chaque appel se divise en appels plus petits ; les réponses reviennent depuis les cas de base.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Écrivez une fonction récursive sum_to(n) qui retourne 1 + 2 + ... + n. Le cas de base est sum_to(0) qui est 0.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Écrivez une power(base, exp) récursive qui retourne base élevé à la puissance exp. Le cas de base est exp == 0, ce qui donne 1.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Écrivez une fonction récursive count_up(n) qui retourne la liste [1, 2, ..., n]. Le cas de base est count_up(0) qui est la liste vide [].
Cliquez sur Exécuter pour voir le résultat ici.