Récursivité et pile d'appels en JavaScript

La récursivité est un concept fondamental en JavaScript qui permet aux fonctions de s'appeler elles-mêmes. Cette méthode est essentielle pour résoudre des problèmes pouvant être décomposés en tâches plus simples et répétitives. Cet article offre une vue d'ensemble complète de la récursivité, en explorant le contexte d'exécution, la pile d'appels et ses applications dans le parcours de structures récursives.

Qu'est-ce que la récursivité ?

La récursivité en programmation est une méthode par laquelle une fonction s'appelle elle-même une ou plusieurs fois jusqu'à ce qu'une condition spécifiée soit remplie, moment à partir duquel le reste de chaque répétition est traité. Toute fonction récursive est composée de deux parties distinctes :

1. Cas de base : la condition sous laquelle la fonction arrête de s'appeler et retourne une valeur directement. Sans cas de base, la fonction s'appellerait indéfiniment.
2. Cas récursif : lorsque le cas de base n'est pas atteint, la fonction se rappelle elle-même avec un argument plus petit ou plus simple qui la rapproche du cas de base.

La règle la plus importante de la récursivité : chaque appel récursif doit progresser vers le cas de base. Si ce n'est pas le cas, on obtient une récursion infinie et le programme plante avec un dépassement de pile.

Voici le plus petit exemple utile possible — additionner les nombres de 1 à n :

Pour calculer sumTo(5), la fonction a besoin de sumTo(4), qui a besoin de sumTo(3), et ainsi de suite jusqu'à sumTo(1), qui retourne 1 directement. La chaîne se déroule ensuite en sens inverse : chaque appel ajoute son propre nombre et retourne le résultat à son appelant.

La même logique peut toujours être écrite avec une boucle à la place. Comparez la version récursive ci-dessus avec cette version itérative :

Les deux produisent le même résultat. La version récursive est plus courte et se rapproche davantage de la définition mathématique ; la version itérative utilise un seul appel de fonction et une quantité fixe de mémoire. Nous comparons les deux plus en détail dans Récursivité vs Itération ci-dessous.

Contexte d'exécution et pile d'appels

Lorsqu'une fonction s'exécute en JavaScript, le moteur crée un contexte d'exécution (parfois appelé cadre de pile) : un enregistrement interne contenant les variables locales de cet appel, ses paramètres et la ligne exacte où l'exécution se trouve actuellement.

La pile d'appels est une pile de ces cadres. Elle fonctionne selon le principe « dernier entré, premier sorti » :

• Lorsqu'une fonction est appelée, son cadre est empilé au sommet de la pile.
• Lorsqu'une fonction retourne, son cadre est dépilé, et le contrôle revient au cadre situé en dessous — exactement là où il s'était arrêté.

Dans la récursivité, chaque appel à la fonction empile un tout nouveau cadre avec sa propre copie des paramètres. Ainsi, sumTo(3) produit trois cadres empilés avant qu'aucun d'eux ne retourne :

sumTo(1)   ← sommet de la pile, retourne 1 en premier
sumTo(2)
sumTo(3)   ← base, l'appel original, retourne en dernier

Une fois que sumTo(1) atteint le cas de base et retourne, son cadre est dépilé, sumTo(2) reprend et retourne, puis sumTo(3). C'est pourquoi la profondeur de la récursion détermine directement la quantité de mémoire utilisée par la pile d'appels : n appels récursifs signifie n cadres actifs en même temps.

Exemple : Rêves imbriqués

Imaginez un scénario où un personnage dans une histoire s'endort et rêve qu'il est quelqu'un d'autre, qui à son tour s'endort pour rêver d'un autre personnage, et ainsi de suite. Chaque niveau de rêve représente un appel récursif, et se réveiller de chaque niveau de rêve représente le dépilage d'un contexte d'exécution de la pile d'appels.

Dans la fonction dream(level) fournie, le cas de base et le cas récursif sont clairement définis :

• Cas de base : Cela se produit lorsque level === 0. C'est la condition qui arrête la récursion de se poursuivre indéfiniment. Dans ce cas, lorsque level atteint 0, la fonction affiche "Wake up!" et cesse de faire d'autres appels récursifs.
• Cas récursif : Il est défini lorsque level > 0. Dans cette situation, la fonction affiche le level courant, puis s'appelle elle-même avec level - 1, réduisant ainsi le level d'un à chaque appel. Cela continue jusqu'à ce que la condition du cas de base soit atteinte.

Ces deux parties fonctionnent ensemble pour s'assurer que la fonction s'exécute correctement et se termine éventuellement.

Parcours récursifs

Le parcours récursif est une technique souvent utilisée avec des structures contenant plusieurs niveaux d'objets imbriqués, tels que des arbres ou des répertoires. Cette méthode est idéale pour effectuer des opérations comme la recherche ou la construction d'une structure visuelle à partir de composants imbriqués.

Exemple : Parcours d'un système de fichiers

Voici comment vous pourriez utiliser la récursivité pour parcourir un système de fichiers, en listant tous les fichiers de chaque répertoire :

Dans la fonction listFiles(directory) partagée, la récursion implique de parcourir une structure de répertoires :

• Cas de base : Fait intéressant, la condition d'arrêt de cette fonction n'est pas explicitement énoncée comme un cas de base traditionnel (comme une instruction if qui termine la récursion). Au lieu de cela, elle s'arrête naturellement de récurser lorsqu'elle rencontre un répertoire sans sous-répertoires supplémentaires (c'est-à-dire que directory.directories est un array vide). En effet, la méthode forEach sur un array vide ne génère aucun appel récursif supplémentaire.
• Cas récursif : Le cas récursif est explicitement invoqué avec directory.directories.forEach(listFiles);. Cela se produit lorsqu'un répertoire contient un ou plusieurs sous-répertoires, et listFiles est appelé récursivement pour chaque sous-répertoire. Chaque appel récursif traite les fichiers et répertoires de ce sous-répertoire, s'enfonçant continuellement dans la structure jusqu'à ce qu'il n'y ait plus de sous-répertoires (cas de base implicite).

Cette fonction démontre efficacement comment la récursivité peut naviguer dans des structures imbriquées complexes en s'appelant elle-même pour gérer des tâches similaires à chaque niveau d'imbrication.

Structures récursives

Les structures récursives sont des structures auto-référentielles où chaque partie est définie en termes de parties similaires. Les exemples courants incluent les organigrammes, les arbres binaires, et bien d'autres.

Exemple : Organigramme

Considérez un organigramme où chaque manager peut avoir plusieurs subordonnés qui peuvent eux-mêmes être des managers.

Dans la fonction showOrgChart(employee), la récursion est structurée pour visualiser un organigramme :

• Cas de base : Similaire à l'exemple précédent de listFiles, le cas de base n'est pas explicitement énoncé comme un point d'arrêt conditionnel dans la fonction. Au lieu de cela, la récursion se termine naturellement lorsqu'un employé n'a pas de subordonnés (employee.subordinates est un array vide). La méthode forEach n'exécute aucune itération lorsque l'array est vide, donc aucun appel récursif supplémentaire n'est effectué.
• Cas récursif : Le comportement récursif se produit avec la ligne employee.subordinates.forEach(showOrgChart). Cela signifie que chaque fois qu'un employé a un ou plusieurs subordonnés, la fonction est appelée récursivement pour chaque subordonné. Cette récursion continue jusqu'en bas de la hiérarchie, enregistrant le nom et le poste de chaque subordonné, jusqu'à ce qu'elle atteigne des employés sans subordonnés (cas de base implicite).

Cette fonction fournit une démonstration claire de la façon dont la récursivité peut être utilisée pour naviguer et afficher des structures hiérarchiques telles que des organigrammes, où chaque niveau de récursion plonge plus profondément dans la structure.

Récursivité vs Itération

Toute fonction récursive peut être réécrite sous forme de boucle, et toute boucle peut être réécrite sous forme de récursion. Choisir entre les deux est un compromis :

Une bonne règle pratique : optez pour la récursivité lorsque les données elles-mêmes sont récursives (arbres, objets imbriqués, le système de fichiers), et optez pour une boucle lorsque vous ne faites que répéter une étape un nombre de fois connu. La factorielle ci-dessous est naturellement récursive, mais une boucle la gère tout aussi bien — et survit à des entrées bien plus grandes :

Dépassement de pile et limites de profondeur

Parce que chaque appel récursif ajoute un cadre à la pile d'appels, la récursivité est bornée par la profondeur à laquelle la pile peut croître. Chaque moteur JavaScript a une taille de pile maximale (le nombre exact varie selon le moteur et la plateforme — souvent quelques milliers à des dizaines de milliers de cadres). La dépasser provoque l'exception suivante :

RangeError: Maximum call stack size exceeded

Les deux causes les plus courantes sont un cas de base manquant ou inaccessible (récursion infinie) et une récursion légitimement profonde sur un très grand ensemble de données. Cet exemple omet délibérément un cas de base fonctionnel afin que la pile se remplisse :

Pour éviter les dépassements de pile :

• Incluez toujours un cas de base que la récursion est garantie d'atteindre.
• Pour les problèmes très profonds ou non bornés, convertissez la récursion en boucle, qui n'a pas de limite de profondeur de ce type.
• Pour les structures de données qui peuvent être arbitrairement profondes, envisagez une pile explicite (un array sur lequel vous faites push/pop) plutôt que la pile d'appels.

Quand utiliser la récursivité

La récursivité est particulièrement utile lorsque vous pouvez décomposer une tâche en sous-tâches plus petites similaires à la tâche globale. Elle est puissante pour :

• Trier des données (comme avec le tri fusion ou le tri rapide)
• Parcourir des arbres, des graphes et des itérables imbriqués
• Manipuler des données structurées complexes telles que JSON ou le DOM

Cependant, il est crucial de s'assurer que chaque appel récursif progresse vers le cas de base afin d'éviter une récursion infinie et des erreurs potentielles de dépassement de pile.

Sujets connexes

• Fonctions JavaScript — comment les fonctions sont déclarées et appelées.
• Expressions de fonction — fonctions stockées dans des variables, que les fonctions récursives utilisent souvent.
• Itérables — le parcours récursif se combine naturellement avec les données itérables.
• Boucles JavaScript — l'alternative itérative à la récursivité.

Conclusion

Comprendre la récursivité et la pile d'appels en JavaScript améliore votre capacité à résoudre des problèmes complexes de manière efficace et efficiente. Avec de la pratique, la récursivité peut devenir un outil précieux dans votre arsenal de programmation, vous permettant d'écrire un code plus propre et plus efficace. Que ce soit pour parcourir des structures de données ou implémenter des algorithmes complexes, maîtriser la récursivité élèvera sans aucun doute vos compétences en codage.

Pratique