Recursion · Récursivité
| English | Français |
|---|---|
| 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éroulement |
A method that calls itself
- Recursion 递归 is when a method calls itself to solve a smaller version of the same problem.
- Every recursion needs two parts: a base case 基准情形 and a recursive case 递归情形.
- The base case stops the recursion — a small input the method answers directly.
- The recursive case calls the method again on a smaller input.
Une méthode qui s'appelle elle-même
- Récursivité 递归 est lorsqu'une méthode s'appelle elle-même pour résoudre une version plus petite du même problème.
- Toute récursivité 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.
The base case
- Without a base case, a method calls itself forever — a
StackOverflowError. - The base case handles the smallest input without another call.
- Example:
factorial(0)returns1directly — no more calls. - Always check: does every path eventually reach the base case?
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 ?
The recursive case
- The recursive case does a little work, then calls itself on a smaller input.
factorial(n)returnsn * factorial(n - 1)— the input shrinks by one each call.- Each call waits for the smaller call to return before finishing.
- The calls stack up, hit the base case, then unwind 回退 back to the top.
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 retombent 回退 vers le haut.
How the calls stack
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)returns1; then the stack unwinds:1, 1, 2, 6.- Each call keeps its own copy of the parameters until it returns.
- Tracing a recursion means following the calls down, then the returns up.
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.
Every recursion needs a base case that stops it — and each recursive call must move TOWARD that base case (a smaller input). Miss the base case, or call on the same or a larger input, and the method recurses forever until a StackOverflowError. Trace by following calls down to the base case, then the returns back up.
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 by recursion:
- Base case:
if (n == 0) return 0; - Recursive case:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
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.
Recursion is a method calling itself on a smaller input. It needs a base case (stops directly, no more calls) and a recursive case (does a little work, then recurses on a smaller input). Calls stack down to the base case, then unwind back up. Miss the base case and you get a StackOverflowError.
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 · factorial(3) se déroule depuis le cas de base vers le haut
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6. · fact(0) retourne 1 (cas de base) ; chaque parent multiplie : 1, 1, 2, 6.
A recursive method is one that... · Une méthode récursive est une qui...
Recursion = a method calling itself. · Récursivité = une méthode s'appelant elle-même.
The base case is... · Le cas de base est...
The base case stops the recursion. · Le cas de base arrête la récursion.
A recursion with no reachable base case causes... · Une récursion sans cas de base atteignable provoque...
It recurses forever until the stack overflows. · Elle récurse indéfiniment jusqu'à ce que la pile déborde.
The recursive case must call itself on... · Le cas récursif doit s'appeler lui-même sur...
Each call must shrink toward the base case. · Chaque appel doit rétrécir vers le cas de base.
If factorial(0)=1 and factorial(n)=nfactorial(n-1), what is factorial(3)? · Si factorial(0)=1 et factorial(n)=nfactorial(n-1), quelle est factorial(3) ?
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns. · Chaque appel récursif garde sa propre copie de ses paramètres jusqu'à son retour.
Calls stack independently, then unwind. · Appels empilés indépendamment, puis déroulement.