Recursion · Récursivité
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · Cette page nécessite un navigateur récent (avec support SharedArrayBuffer). Veuillez mettre à jour Chrome, Edge, Firefox ou Safari vers la dernière version.
English
A function that calls itself
- Recursion is when a function calls itself.
- Each call should work on a smaller version of the problem.
- Done right, the problem shrinks until it is trivial to solve.
Français
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.
English
Base case and recursive case
- The base case is the simplest case — it stops the recursion.
- The recursive case calls the function again on a smaller input.
- Without a base case the function never stops (an error).
Français
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)
English
A worked example: factorial
- The factorial
n!meansn × (n-1) × ... × 1. - In recursive form:
n! = n × (n-1)!, and the base case is0! = 1. - Each call multiplies
nby the factorial of one less.
Français
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))
English
How the computer runs it
- Each call is paused on a call stack while it waits for the inner call.
- When the base case returns, the paused calls finish one by one.
- Too many calls overflow the stack — Python raises a
RecursionError.
Français
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.
English
In Cambridge pseudocode
- A recursive function names its base case and recursive case clearly.
Français
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
English
Common mistakes
- Every recursion needs a base case, or it overflows the call stack.
- Each call must move closer to the base case.
Français
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.
English
Now you try
- Give each function a base case and a recursive case.
- Press Check answer to test your code.
Français
À 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.
Explore · Explorer
Recursion returns from the leaves · La récursion revient des feuilles
Each call splits into smaller calls; answers return up from the base cases. · Chaque appel se divise en appels plus petits ; les réponses reviennent depuis les cas de base.
Write a recursive sum_to(n) that returns 1 + 2 + ... + n. The base case is sum_to(0) which is 0. · Écrivez une fonction récursive sum_to(n) qui retourne 1 + 2 + ... + n. Le cas de base est sum_to(0) qui est 0.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write a recursive power(base, exp) that returns base raised to exp. The base case is exp == 0, which gives 1. · É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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write a recursive count_up(n) that returns the list [1, 2, ..., n]. The base case is count_up(0) which is the empty list []. · É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 [].
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.