Recursion: base case and recursive case · Récursion : cas de base et cas récursif
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 method that calls itself
- Recursion is when a method calls itself to solve a smaller piece of the same problem.
- On the AP CSA exam you mostly trace recursion (follow the calls by hand). Writing small recursive methods helps you trace well.
- Every recursive method needs two parts: a base case and a recursive case.
Français
Une méthode qui s'appelle elle-même
- La récursion est le fait qu'une méthode s'appelle elle-même pour résoudre une sous-partie plus petite du même problème.
- À l'examen AP CSA, vous devez surtout tracer la récursion (suivre les appels à la main). Écrire de petites méthodes récursives facilite ce tracé.
- Toute méthode récursive nécessite deux parties : un cas de base et un cas récursif.
English
Base case and recursive case
- Base case: the simplest input, where you return an answer without calling yourself. This stops the recursion.
- Recursive case: you call the same method with a smaller input, then build the answer.
- Without a base case, the method calls forever and crashes (a stack overflow).
Français
Cas de base et cas récursif
- Cas de base : l'entrée la plus simple, où vous retournez une réponse sans vous appeler. Cela arrête la récursion.
- Cas récursif : vous appelez la même méthode avec une entrée plus petite, puis vous construisez la réponse.
- Sans cas de base, la méthode s'appelle indéfiniment et plante (une surcharge de pile ou stack overflow).
English
Example: factorial
factorial(n)meansn * (n-1) * ... * 1. For examplefactorial(4) = 24.- Base case:
factorial(1)is1. - Recursive case:
factorial(n)isn * factorial(n - 1).
Français
Exemple : factorielle
factorial(n)vautn * (n-1) * ... * 1. Par exemplefactorial(4) = 24.- Cas de base :
factorial(1)vaut1. - Cas récursif :
factorial(n)vautn * factorial(n - 1).
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
English
How the calls unwind
- Each call waits for the smaller call to finish. Then it multiplies and returns.
- Trace
factorial(3). Calls go down, then answers come back up.
Français
Comment les appels se déroulent
- Chaque appel attend que l'appel plus petit se termine. Puis il multiplie et retourne.
- Tracez
factorial(3). Les appels descendent, puis les réponses remontent.
factorial(3) = 3 * factorial(2) <- waits
factorial(2) = 2 * factorial(1) <- waits
factorial(1) = 1 <- base case, returns 1
factorial(2) = 2 * 1 = 2 <- returns 2
factorial(3) = 3 * 2 = 6 <- returns 6
English
Example: sum to n
sumTo(n)adds1 + 2 + ... + n. For examplesumTo(4) = 10.- Base case:
sumTo(0)is0(nothing to add). - Recursive case:
sumTo(n)isn + sumTo(n - 1).
Français
Exemple : somme jusqu'à n
sumTo(n)ajoute1 + 2 + ... + n. Par exemplesumTo(4) = 10.- Cas de base :
sumTo(0)vaut0(rien à ajouter). - Cas récursif :
sumTo(n)vautn + sumTo(n - 1).
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
English
Recursion over an array
- We can also recurse with an index that moves toward the end.
- Base case: when the index is past the last spot, return
0. - Recursive case: add
a[i]to the sum of the rest,arraySum(a, i + 1).
Français
Récursion sur un tableau
- Nous pouvons aussi récuser avec un index qui avance vers la fin.
- Cas de base : lorsque l'index est au-delà de la dernière position, retournez
0. - Cas récursif : ajoutez
a[i]à la somme du reste,arraySum(a, i + 1).
English
- To sum the whole array you start at index
0:arraySum(a, 0). - Each call handles one value and trusts the next call for the rest.
Français
public class Recursion {
public static int arraySum(int[] a, int i) {
if (i >= a.length) { // base case: past the end
return 0;
}
return a[i] + arraySum(a, i + 1);
}
}
- Pour sommer tout le tableau, commencez à l'index
0:arraySum(a, 0). - Chaque appel gère un seul élément et fait confiance à l'appel suivant pour le reste.
English
Common mistakes
- Recursion needs a base case, or it throws StackOverflowError.
- Each call must move closer to the base case.
Français
Erreurs courantes
- La récursion a besoin d'un cas de base, sinon elle lance StackOverflowError.
- Chaque appel doit se rapprocher du cas de base.
English
Now you try
- Each task gives you a method skeleton with a TODO. Write the base case and the recursive case.
- A hidden Harness calls your method with several values and checks the result.
- Press Run to compile, then Check answer.
Français
À vous maintenant
- Chaque exercice vous donne un squelette de méthode avec un TODO. Écrivez le cas de base et le cas récursif.
- Un Harness caché appelle votre méthode avec plusieurs valeurs et vérifie le résultat.
- Appuyez sur Run pour compiler, puis sur Check answer.
Explore · Explorer
Recursion: base + recursive case · Récursion : cas de base + cas récursif
Calls split until a base case, then answers return up. · Les appels se divisent jusqu'à un cas de base, puis les réponses remontent.
Complete factorial(int n) so it returns n * (n-1) * ... * 1 using recursion. Use a base case for n <= 1. The checker tests several values. · Complétez factorial(int n) pour qu'elle retourne n * (n-1) * ... * 1 en utilisant la récursion. Utilisez un cas de base pour n <= 1. Le vérificateur teste plusieurs valeurs.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete sumTo(int n) so it returns 1 + 2 + ... + n using recursion. Use a base case for n <= 0. The checker tests several values. · Complétez sumTo(int n) pour qu'elle retourne 1 + 2 + ... + n en utilisant la récursion. Utilisez un cas de base pour n <= 0. Le vérificateur teste plusieurs valeurs.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete arraySum(int[] a, int i) so it returns the sum of a[i] to the end, using recursion. Base case: when i is past the last spot, return 0. The checker tests several arrays. · Complétez arraySum(int[] a, int i) pour qu'il retourne la somme de a[i] à la fin, en utilisant la récursion. Cas de base : lorsque i dépasse la dernière position, retournez 0. Le testeur vérifie plusieurs tableaux.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.