Récursion : cas de base et cas récursif
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.
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).
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
}
}
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
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
}
}
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).
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.
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.
À 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.
- Utilisez Vérifier la réponse pour compiler votre code avec les tests fournis et voir les résultats. Conservez les interfaces de classe et de méthode montrées dans l'en-tête.
Récursion : cas de base + cas récursif
Les appels se divisent jusqu'à un cas de base, puis les réponses remontent.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
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
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.
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
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.
Cliquez sur Exécuter pour voir le résultat ici.