La récursion en Java

La récursion se produit lorsqu'une méthode s'appelle elle-même. C'est une façon naturelle d'exprimer des problèmes dont la structure se répète à une échelle plus petite — compter à rebours, parcourir un arbre, calculer une factorielle, inverser une chaîne.

Toute méthode récursive comporte deux parties : un cas de base qui retourne directement sans récursion, et un cas récursif qui appelle la méthode sur une portion plus petite du problème. Une erreur dans l'une ou l'autre partie entraîne soit une réponse incorrecte, soit une exécution infinie (jusqu'à ce que la JVM fasse déborder la pile).

Un premier exemple : la factorielle

La factorielle de n est n × (n-1) × (n-2) × … × 1. Par définition, 0! = 1. Cette définition est elle-même récursive : n! = n × (n-1)!.

La traduction Java est directe :

public static int factorial(int n) {
  if (n == 0) return 1;            // base case
  return n * factorial(n - 1);      // recursive case
}

L'appel de factorial(4) produit :

factorial(4)
  = 4 * factorial(3)
  = 4 * 3 * factorial(2)
  = 4 * 3 * 2 * factorial(1)
  = 4 * 3 * 2 * 1 * factorial(0)
  = 4 * 3 * 2 * 1 * 1
  = 24

Chaque appel attend sur la pile que le suivant retourne. Quand factorial(0) retourne enfin 1, les réponses remontent en cascade le long de la chaîne.

Le cas de base est indispensable

Sans cas de base, la méthode n'a rien pour arrêter la récursion. L'erreur classique :

public static int factorial(int n) {
  return n * factorial(n - 1);    // no base case
}

Ceci récurse indéfiniment — enfin, jusqu'à ce que la pile d'appels soit épuisée et que la JVM lève une StackOverflowError. Le cas de base est ce qui termine la chaîne ; le cas récursif est ce qui progresse vers lui.

L'autre erreur classique est un cas de base que la récursion n'atteint jamais :

public static int factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n + 1);    // wrong direction
}

factorial(4) ici essaierait factorial(5), factorial(6), … et planterait. L'appel récursif doit rapprocher l'argument du cas de base.

Récursion sur les entiers : compte à rebours

Un deuxième exemple simple pour la clarté — afficher les nombres de n jusqu'à 1 :

public static void countdown(int n) {
  if (n <= 0) return;             // base case
  System.out.println(n);
  countdown(n - 1);                // recursive case
}

countdown(3) affiche 3, 2, 1. Inversez l'ordre pour afficher 1, 2, 3 :

public static void countup(int n) {
  if (n <= 0) return;
  countup(n - 1);                  // recurse first, print after
  System.out.println(n);
}

Même récursion, ordre d'affichage différent — parce que l'appel récursif se produit avant l'affichage. La leçon : ce que vous faites avant l'appel récursif s'exécute à la descente, ce que vous faites après s'exécute à la remontée.

Récursion sur les chaînes : inversion

On peut concevoir l'inversion d'une chaîne comme « enlever le premier caractère, inverser le reste, ajouter le premier caractère à la fin » :

public static String reverse(String s) {
  if (s.length() <= 1) return s;            // base case
  return reverse(s.substring(1)) + s.charAt(0);
}

reverse("cat") → reverse("at") + 'c' → reverse("t") + 'a' + 'c' → "t" + 'a' + 'c' → "tac".

C'est élégant mais inefficace — chaque appel récursif alloue une nouvelle sous-chaîne. Une boucle avec StringBuilder serait plus rapide. La récursion est souvent l'expression la plus claire d'une idée ; ce n'est pas toujours l'implémentation la plus rapide.

Fibonacci et le coût de la récursion

La suite de Fibonacci est 0, 1, 1, 2, 3, 5, 8, 13, …, définie par fib(n) = fib(n-1) + fib(n-2). La traduction directe :

public static long fib(int n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

C'est correct mais exponentiellement lent — fib(40) prend déjà un temps notable, fib(50) est douloureux. L'arbre de récursion recalcule les mêmes sous-problèmes des milliards de fois (fib(5) appelle seul fib(2) trois fois). La solution en code réel est soit la mémoïsation, soit une boucle simple.

La mémoïsation conserve la structure récursive mais met en cache chaque résultat la première fois qu'il est calculé, de sorte que chaque sous-problème ne s'exécute qu'une fois :

public static long fibMemo(int n, long[] cache) {
  if (n < 2) return n;
  if (cache[n] != 0) return cache[n];      // already computed
  return cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
}
// call as: fibMemo(50, new long[51])

Une boucle simple supprime entièrement la récursion et utilise une mémoire constante :

public static long fibLoop(int n) {
  long a = 0, b = 1;
  for (int i = 0; i < n; i++) {
    long next = a + b;
    a = b;
    b = next;
  }
  return a;
}

Savoir quand la récursion est le mauvais outil est aussi important que savoir quand elle est le bon.

Récursion vs itération

Toute méthode récursive peut être réécrite sous forme de boucle, et toute boucle peut être réécrite en récursion — elles ont une puissance équivalente. Le choix porte sur la clarté et le coût :

• Optez pour la récursion lorsque les données sont elles-mêmes récursives (arbres, dossiers imbriqués, JSON) ou lorsque la définition récursive est plus lisible que la boucle, comme avec factorial ou reverse.
• Optez pour une boucle lorsque la récursion serait suffisamment profonde pour risquer une StackOverflowError, ou lorsqu'une version itérative est tout aussi lisible et évite le surcoût par appel, comme avec fib.

Quand les deux sont aussi clairs, préférez la boucle en Java : elle n'a pas de limite de profondeur de pile ni de coût de cadre d'appel.

StackOverflowError

Chaque appel en attente utilise une portion de la pile de la JVM. Avec la taille de pile par défaut, vous pouvez généralement imbriquer quelques milliers d'appels avant que les choses ne se gâtent :

factorial(100000);    // StackOverflowError

Java ne fait pas d'optimisation des appels de queue — même un appel récursif qui est la dernière chose que fait la méthode consomme encore un cadre de pile. Si le problème peut nécessiter une récursion très profonde, passez à une boucle ou utilisez un Deque explicite comme votre propre pile.

Un exemple complet

Et ensuite

Vous avez défini des méthodes, passé des paramètres, surchargé des noms et utilisé la récursion. Le prochain concept est la portée — quelles parties d'une méthode peuvent voir quelles variables, et ce qui se passe lorsqu'un nom apparaît à plusieurs endroits. Continuez avec le chapitre sur la portée des variables.

Pratique