Récursivité en JavaScript : une fonction qui s'appelle elle-même

Compter les fichiers d'un dossier qui contient des dossiers, parcourir un menu à plusieurs niveaux, aplatir une structure imbriquée : aucune boucle simple ne suffit, parce qu'on ne sait pas à l'avance combien de niveaux existent.

La récursivité répond exactement à cette forme de problème : résoudre un cas en le ramenant à une version plus petite de lui-même.

Définition

Une fonction est récursive quand elle s'appelle elle-même. Elle repose sur deux morceaux indissociables : un cas de base, qui renvoie une valeur sans se rappeler, et un cas récursif, qui se rappelle sur une version réduite du problème.

function factorielle(n) {
  if (n <= 1) return 1;           // cas de base
  return n * factorielle(n - 1);  // cas récursif
}

console.log(factorielle(5)); // 120

Sans le cas de base, la fonction ne s'arrête jamais et la Pile d'appels (call stack) déborde en quelques millisecondes. C'est la première chose à écrire, avant même l'appel récursif.

Là où elle est vraiment supérieure

La factorielle sert à expliquer, pas à convaincre : une boucle la ferait aussi bien. La récursivité gagne quand la structure elle-même est imbriquée.

const menu = {
  nom: "Racine",
  enfants: [
    { nom: "Formations", enfants: [{ nom: "JavaScript", enfants: [] }] },
    { nom: "Blog", enfants: [] },
  ],
};

function compter(noeud) {
  return 1 + noeud.enfants.reduce((n, sous) => n + compter(sous), 0);
}

console.log(compter(menu)); // 4

Écrire la même chose avec une boucle demanderait de gérer soi-même une liste des nœuds restant à visiter. La version récursive tient en une ligne parce qu'elle laisse la pile faire ce travail.

Récursivité ou boucle ?

• Structure imbriquée de profondeur inconnue : la récursivité, sans hésiter.
• Parcours linéaire d'une liste : une boucle ou un Array.reduce(), plus direct et sans limite de profondeur.
• Très grands volumes : la boucle, car chaque appel récursif consomme une entrée de pile.

Questions fréquentes

L'ordre de grandeur tourne autour de dix mille appels imbriqués, sans garantie : la limite dépend du moteur et de la mémoire disponible. Un arbre de fichiers ou un menu n'en approchera jamais. Une liste de cent mille éléments parcourue récursivement, si, et il faut alors passer à une boucle.

La spécification la prévoit, mais aucun moteur grand public ne l'a implémentée en dehors de Safari. Écrire une fonction en récursion terminale, où l'appel récursif est la toute dernière opération, ne protège donc pas du débordement. Il ne faut pas compter dessus.

Affichez les arguments à chaque entrée dans la fonction : si la valeur ne se réduit pas d'un appel à l'autre, le cas de base ne sera jamais atteint. C'est presque toujours l'explication, et le correctif tient dans la condition d'arrêt ou dans la valeur transmise à l'appel suivant.