La récursivité en Java : compréhension, exemples et compromis

Récursivité en Java

Ce guide explique les méthodes récursives de Java, présente l'exemple classique du factoriel, et évalue les avantages et inconvénients de la récursivité.

En Java, une méthode qui s'appelle elle-même est appelée méthode récursive, et la technique globale est connue sous le nom de récursivité. Une illustration simple du monde réel est deux miroirs se faisant face : chaque reflet est une autre image de miroir, se répétant jusqu'à ce que la lumière soit absorbée.

---

Comment fonctionne la récursivité

Dans l'illustration ci-dessus, la méthode recurse() est invoquée depuis main() – un appel normal. À l'intérieur de recurse(), la même méthode s'appelle à nouveau, créant un appel récursif. Pour éviter une boucle infinie, chaque appel récursif doit inclure une condition d'arrêt, généralement implémentée avec une instruction if…else.

---

Exemple : Factoriel d'un nombre avec récursivité

class Factorial { static int factorial(int n) { if (n != 0) // condition d'arrêt return n * factorial(n - 1); // appel récursif else return 1; } public static void main(String[] args) { int number = 4, result; result = factorial(number); System.out.println(number + " factorial = " + result); } }

Sortie :

4 factorial = 24

La méthode factorial() est appelée depuis main() avec l'argument number. À l'intérieur de factorial(), la ligne

return n * factorial(n-1);

fait que la méthode s'invoque elle-même avec une valeur décrémentée. En partant de n = 4, les appels progressent : 4 → 3 → 2 → 1 → 0. Quand n atteint 0, la condition if échoue, retournant 1. Le produit accumulé se propage ensuite vers le haut de la pile d'appels jusqu'à main().

---

Comment s'exécute le programme factoriel

L'image ci-dessous illustre l'évolution de la pile d'appels pendant l'exécution.

---

Avantages et inconvénients de la récursivité

• Avantages : Simplifie le code pour les problèmes qui s'adaptent naturellement aux motifs récursifs (parcours d'arbres, génération combinatoire). Résulte souvent en implémentations plus courtes et plus lisibles.
• Inconvénients : Chaque appel récursif consomme de l'espace de pile ; une récursivité profonde peut mener à un débordement de pile. Les solutions récursives sont généralement moins efficaces en mémoire et peuvent être plus lentes que les équivalents itératifs.

Dans l'ensemble, la récursivité offre des solutions élégantes au coût d'une utilisation mémoire plus élevée et d'une surcharge de performance potentielle. Pour de nombreux cas d'usage, surtout ceux à profondeur limitée, le compromis en vaut la peine.

Lecture recommandée : Quels sont les avantages et inconvénients de la récursivité ?