Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Récursivité : cas de base, pile d'appels, retour sur trace

Récursivité : cas de base, pile d'appels, retour sur trace

Récursivité, arbres et graphesavance

Une fonction récursive a deux parties, et l'ordre d'écriture compte :

static long factorielle(int n) {
    if (n <= 1) return 1;              // 1. cas de base, toujours en premier
    return n * factorielle(n - 1);     // 2. cas récursif, sur un problème plus petit
}

Le retour sur trace ajoute une troisième étape : défaire.

static void permutations(int[] t, List<Integer> courant, boolean[] utilise, List<List<Integer>> r) {
    if (courant.size() == t.length) {
        r.add(new ArrayList<>(courant));      // COPIE : sinon toutes les solutions
        return;                                // pointeraient sur la même liste
    }
    for (int i = 0; i < t.length; i++) {
        if (utilise[i]) continue;
        utilise[i] = true;  courant.add(t[i]);          // choisir
        permutations(t, courant, utilise, r);           // explorer
        courant.remove(courant.size() - 1);  utilise[i] = false;   // DÉFAIRE
    }
}

Choisir, explorer, défaire : ce triptyque résout permutations, combinaisons, sous-ensembles, sudoku, n-reines.

La limite à connaître : la pile d'appels de la JVM tient quelques dizaines de milliers de niveaux. Java n'optimise pas la récursivité terminale. Sur de grandes profondeurs, il faut une pile explicite.

Les termes à connaître

Cas de base

La condition qui arrête la récursion. Sans lui — ou s'il n'est jamais atteint —, c'est le StackOverflowError. On l'écrit avant le cas récursif.

Cas récursif

L'appel sur un problème strictement plus petit. « Plus petit » doit être garanti à chaque appel, sinon la récursion ne termine pas.

Pile d'appels

Chaque appel empile un cadre contenant ses variables locales. La profondeur est limitée : environ 10 000 à 20 000 niveaux par défaut sur la JVM.

StackOverflowError

L'erreur levée quand la pile d'appels est saturée : cas de base manquant, récursion trop profonde, ou cycle dans les données.

Retour sur trace (*backtracking*)

Explorer une possibilité, puis défaire le choix avant d'explorer la suivante. Le motif des permutations, des combinaisons et du sudoku.

Récursivité terminale

Un appel récursif en dernière position. Certains langages l'optimisent en boucle ; Java ne le fait pas — la profondeur reste un risque.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.