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.
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.