Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

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

recursion

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.

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.

Sources