CKTIS / Java
Récursion et pile d’appels
Récursion et pile d’appels: La récursion apparaît lorsqu’une méthode s’appelle directement ou indirectement ; chaque appel possède une frame de pile, donc il faut un cas de base et une progression.
Version : Java SE 21 (JLS and Java SE API); examples verified on the repository Java runtime
Syntaxe
recursionLa récursion apparaît lorsqu’une méthode s’appelle directement ou indirectement ; chaque appel possède une frame de pile, donc il faut un cas de base et une progression.
Utilise-la pour des arbres bornés et diviser-pour-régner ; remplace un parcours linéaire profond par une itération avec Deque.
Java ne garantit aucune optimisation d’appel terminal ; une récursion correcte mais profonde peut donc finir par StackOverflowError.
Une entrée vide doit atteindre le cas de base, et un graphe cyclique exige un ensemble visited pour terminer.
Deux cas de base terminent les appels : factorial(5) affiche 120 et l’algorithme d’Euclide récursif gcd(48,18) affiche 6.
Exemples
public class Main {
static int factorial(int n) {
return n <= 1 ? 1 : n * factorial(n - 1);
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
System.out.println(factorial(5));
System.out.println(gcd(48, 18));
}
}
Résultat
120 6
Deux cas de base terminent les appels : factorial(5) affiche 120 et l’algorithme d’Euclide récursif gcd(48,18) affiche 6.