Récursivité
Introduit| English | Sens |
|---|---|
| Recursion/rɪˈkɜːʃn/ | Récursivité |
| base case/beɪs keɪs/ | cas de base |
| recursive case/rɪˈkɜːsɪv keɪs/ | cas récursif |
| unwind/ʌnˈwaɪnd/ | dépilement |
Une méthode qui s'appelle elle-même
- La récursion survient lorsqu'une méthode s'appelle elle-même pour résoudre une version plus petite du même problème.
- Toute récursion nécessite deux parties : un cas de base et un cas récursif.
- Le cas de base arrête la récursivité — une petite entrée que la méthode résout directement.
- Le cas récursif appelle la méthode à nouveau sur une entrée plus petite.
Le cas de base
- Sans cas de base, une méthode s'appelle elle-même à l'infini — une
StackOverflowError. - Le cas de base gère la plus petite entrée sans autre appel.
- Exemple :
factorial(0)renvoie1directement — plus d'appels. - Vérifiez toujours : chaque chemin aboutit-il finalement au cas de base ?

Le tri fusion appelle récursivement chaque moitié, puis fusionne les moitiés triées
Le cas récursif
- Le cas récursif effectue un peu de travail, puis s'appelle lui-même sur une entrée plus petite.
factorial(n)retournen * factorial(n - 1)— l'entrée diminue d'un à chaque appel.- Chaque appel attend que l'appel plus petit retourne avant de se terminer.
- Les appels s'empilent, atteignent le cas de base, puis se déroulent jusqu'au sommet.
Comment les appels s'empilent
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)retourne1; puis la pile retombe :1, 1, 2, 6.- Chaque garde sa propre copie des paramètres jusqu'à son retour.
- Tracer une récursivité consiste suivre les appels vers le bas, puis les retours vers le haut.
Toute récursivité nécessite un cas de base qui l'arrête — et chaque appel récursif doit aller VERS ce cas de base (une entrée plus petite). Manquez le cas de base, ou appelez avec la même ou une entrée plus grande, et la méthode récursive tourne à l'infini jusqu'à une StackOverflowError. Tracez en suivant les appels vers le bas jusqu'au cas de base, puis les retours vers le haut.
sum(n) = 1 + 2 + … + n par récursivité :
- Cas de base :
if (n == 0) return 0; - Cas récursif :
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
Récursivité est une méthode qui s'appelle elle-même sur une entrée plus petite. Elle a besoin d'un cas de base (s'arrête directement, plus d'appels) et d'un cas récursif (fait un peu de travail, puis récurse sur une entrée plus petite). Les appels s'empilent vers le bas jusqu'au cas de base, puis retombent vers le haut. Manquez le cas de base et vous obtenez une StackOverflowError.
factorial(3) unwinds from the base case up
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6.
A recursive method is one that...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Recursion = a method calling itself.
The base case is...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The base case stops the recursion.
A recursion with no reachable base case causes...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
It recurses forever until the stack overflows.
The recursive case must call itself on...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Each call must shrink toward the base case.
If factorial(0)=1 and factorial(n)=n*factorial(n-1), what is factorial(3)?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Calls stack independently, then unwind.