ES6 - De la récursion à la récursion de queue

La prochaine version de JavaScript (ECMAScript 6) introduira une fonctionnalité de programmation incroyablement puissante appelée Tail Recursion, une fonctionnalité qui m’enthousiasme beaucoup. Dans cet article, j’aimerais parler un peu de la récursion par rapport à l’itération, de la récursion de queue et de ce que cela signifie pour l’avenir de JavaScript.

Récursion

La récursivité a toujours été une fonctionnalité puissante de JavaScript, et de nombreux autres langages de programmation, en tant que moyen de résoudre des problèmes en décomposant les choses en versions plus simples/plus petites d’elles-mêmes. Dans le contexte de la programmation, il s’agit d’une fonction qui s’appelle elle-même, mais avec des arguments modifiés ou réduits. La stratégie récursive de résolution des problèmes donne souvent des résultats assez élégants, avec un code plus lisible et plus clair que d’autres approches, telles que le forçage brutal ou l’itération. Cependant, si la tâche à accomplir consiste à explorer de grandes quantités de données imbriquées, nous devons prendre une décision : récursion ou itération ? Commençons par un peu de code…

Voici une fonction factorielle, la quintessence de la récursivité utilisée dans de nombreux langages de programmation - rien d’extraordinaire ou d’excitant.

fonction factorial(n) { return n === 1 ? 1 : n * factorial(n - 1) ; }

Pour parler de la fonction, factorial() prend simplement un argument numérique, disons 6, et multiplie l’argument par la factorielle de l’argument soustrait par 1, qui prend à nouveau cet argument et le multiplie par la factorielle de 1, etc., jusqu’à ce que l’argument soit 1 et que la fonction retourne - hélas, vous avez la récursion.

Le retour de 1 indique la condition de terminaison (ou cas de base) requise par une fonction récursive, tandis que le reste de la fonction continue à s’exécuter et à s’appeler elle-même de manière récursive jusqu’à ce que le cas de base soit satisfait. Bien que cette simple fonction factorielle puisse sembler belle et élégante du point de vue de la propreté, il y a des implications très importantes qui se passent dans les coulisses de la façon dont nous avons exécuté notre appel factoriel. Un bon moyen de comprendre comment factorial() va s’exécuter est de visualiser la pile qui est créée.

Vous trouverez ci-dessous une représentation approximative de ce qui se passe plus ou moins en coulisses lorsque vous exécutez une fonction récursive dans les implémentations actuelles de JavaScript.

factorial(6) // alloue de la mémoire et sauvegarde l'état 6 * factorial(5) // alloue de la mémoire et sauvegarde l'état 6 * (5 * factorial(4)) // alloue de la mém... 6 * (5 * (4 * factorielle(3))) // alloue de la mém... 6 * (5 * (4 * (3 * factorielle(2)))))) // alloue des mem.. // allouer des mem... 6 * (5 * (4 * (3 * (2 * factorielle(1))))) // allouer des mem... 6 * (5 * (4 * (3 * (2 * (1 * factorielle(0)))))) // allocate mem... (max depth) 6 * (5 * (4 * (3 * (2 * (1 * 1))))) 6 * (5 * (4 * (3 * (2 * 1)))) 6 * (5 * (4 * (3 * 2))) 6 * (5 * (4 * 6)) 6 * (5 * 24) 6 * 120 720

Tout d’abord, nous devons nous faire une idée de la façon dont ce calcul est effectué afin de comprendre l’espace et la complexité de la consommation de mémoire. Ci-dessus, nous avons cet arbre récursif en cascade, où chaque appel de fonction est empilé dans la mémoire pour être alloué à l’appel récursif suivant. Chaque récursion occupe de l’espace, car lorsque nous appelons factorial(6), nous accumulons des opérations différées qui seront exécutées une fois que l’appel récursif final sera terminé. Il y a une montée et une descente de l’espace alloué, donc pour factorial(n) nous allouons n places sur la pile. Une représentation graphique de cette consommation de mémoire en fonction de la taille de l’appel récursif pourrait ressembler au graphique ci-dessous.

D’après ce graphique, nous pouvons affirmer que l’utilisation de la mémoire est illimitée (ce qui n’est pas une bonne chose). Remarquez que la consommation de mémoire augmente avec l’ajout de chaque appel récursif. À terme, cette augmentation sans limite de la mémoire va mettre un terme à notre capacité d’exécution en faisant exploser la pile, ce que l’on appelle un débordement de la pile. La quantité de capacité récursive varie en fonction des implémentations des moteurs de navigation et de la taille de leurs piles d’appels respectives. Une façon d’avoir un aperçu des limites de la taille de la pile d’appels des différentes implémentations des navigateurs serait d’envelopper un appel récursif dans un try catch, ce qui permettrait d’attraper notre limite et de préserver notre exécution, voir ci-dessous.

fonction count(num) { try { return count((num || 0) + 1) ; } catch(e) { return num ; } }

Cette fonction continuera à se déplacer jusqu’à ce que la taille de la pile d’appels dépasse la quantité de mémoire, ce qui nous donnera une estimation de la taille de la pile d’appels des environnements respectifs. Essayez-la dans différents navigateurs pour comparer leurs limites respectives.

Itération

Les informations ci-dessus nous amènent à penser que l’utilisation de la récursivité en JavaScript pourrait être jugée peu pratique (en fonction de la taille de la pile d’appels nécessaire), après tout, tout algorithme pouvant être mis en œuvre à l’aide de la récursivité peut également être mis en œuvre à l’aide de l’itération. Voyons un exemple de calcul de la factorielle d’un nombre via l’itération ou la récursion.

// via Iteration function factorial(n) { if (n === 0) { return 1 ; } else { var sum = 1 ; for (var i = 1 ; i <= n ; i++) { sum = sum * i ; } return sum ; } }

À mon avis, la version ci-dessus est moins élégante et moins lisible que la version récursive déclarée plus tôt. De plus, elle n’utilise pas tout à fait l’aspect fonctionnel de JavaScript qui est souvent considéré comme l’une des meilleures parties du langage, si ce n’est la meilleure. Cependant, une approche itérative en boucle du problème factoriel nous empêcherait d’ajouter des éléments à la pile d’appels, ce qui permettrait de limiter la consommation de mémoire.

Quoi qu’il en soit, nous allons prétendre que les boucles sont laides, et nous rappeler que nous aimons le code élégant, propre et lisible, alors revenons à ce style récursif lisse. Pas de problème, ES6 vient à la rescousse avec cette nouvelle fonctionnalité appelée récursion de queue - mais d’abord, qu’est-ce que la récursion de queue ?

Tail Recursion Recursion

Qu’est-ce que la récursivité de queue ? En fait, au lieu d’invoquer la fonction récursive comme instruction de retour (en appelant une nouvelle version d’elle-même), elle fait un saut et réutilise le même contexte (ou enregistrement d’activation) de l’appel récursif précédent, en d’autres termes, pas de coût de mémoire supplémentaire. Cela signifie que si nous utilisons correctement la récursivité de queue dans nos fonctions récursives, l’utilisation de la mémoire restera stable au lieu d’augmenter continuellement à chaque appel récursif. Par exemple, une version récursive de queue correctement implémentée de la fonction factorielle pourrait ressembler à ceci.

Comparez cela au graphique ci-dessus et nous sommes soudain des programmeurs bien plus heureux. Au lieu d’ajouter des appels à la pile et de consommer de la mémoire, les piles et contextes précédents seront libérés (ou réutilisés) et ramassés, ce qui empêchera une croissance continue de l’utilisation de la mémoire. Tout va donc pour le mieux et la récursivité de queue vient sauver la situation (en quelque sorte). Avant d’être trop enthousiastes, nous devons faire quelques mises en garde. Pour que la récursivité de queue soit correcte, nous devons satisfaire à trois conditions.

• être en mode strict

• écrire nos programmes sous la forme d’un appel à la queue

• être dans un environnement optimisé pour les appels de queue (TCO)

La première de ces tâches est facile, si vous souhaitez en savoir plus sur le mode strict, consultez les ressources MDN ici. Je recommande à tous les développeurs JavaScript de l’utiliser.

La seconde tâche, à savoir la forme correcte de l’appel à la queue, est un peu plus délicate. Malheureusement, notre élégante fonction factorielle récursive déclarée précédemment ne serait pas qualifiée pour la récursion de queue même dans un environnement optimisé pour l’appel de queue. Ce n’est pas une forme d’appel de queue correcte, laissez-moi vous expliquer…

Un appel de queue correct est lorsque la dernière chose que fait une fonction est de renvoyer le résultat de l’appel d’une autre fonction. Dans la fonction ci-dessus, le ternaire else en surbrillance renvoie le résultat de n * factorielle(n - 1), en d’autres termes, ce n’est pas une fonction autonome, et par conséquent, elle doit conserver la pile. Un exemple de fonction factorielle avec des appels de queue appropriés (voir ci-dessous), remarquez que le ternaire else renvoie recur(n - 1, n * acc) en tant qu’invocation autonome. Notez que cette version d’une fonction factorielle récursive correctement appelée par la queue est un peu plus compliquée, mais elle serait éligible au TCO et nous donnerait donc la puissance de la récursion par la queue.

// via Tail Recursion function factorial(n) { function recur(n, acc) { return n == 0 ? acc : recur(n-1, n*acc) ; } return recur(n, 1) ; }

Pour plus de clarté, voici un exemple simplifié à l’extrême d’une fonction non récursive sous la forme d’un appel de queue. La fonction ci-dessous a la possibilité d’optimiser l’appel de queue. Dès que foo() exécute bar() comme action finale, bar() peut réutiliser la pile allouée à foo() plutôt que d’en ajouter une nouvelle (et d’augmenter l’utilisation de la mémoire).

fonction foo() // fait quelque chose... return bar() ; // forme correcte d'appel de queue }

Si nous appliquons nos nouvelles optimisations de la mémoire récursive au “monde réel”, nous pourrions constater des avantages substantiels en termes de performances pour parcourir/manipuler des ensembles de données extrêmement volumineux. Pour la majorité d’entre nous, le JavaScript que nous écrivons au quotidien ne bénéficiera pas nécessairement de ces appels récursifs optimisés. Cependant, imaginons que nous soyons confrontés à un problème spécifique nécessitant la traversée d’un arbre de données massif. Un arbre de données où chaque nœud est associé à une quantité substantielle d’informations et de frais généraux - cela vous semble-t-il familier ? Bien sûr, il s’agit de la merveilleuse API que nous connaissons et aimons tous, le DOM ! En tant que développeurs, nos programmes, nos patrons et nos clients nous demandent souvent d’interagir avec le DOM (pensez à l’algorithme de parcours des arbres) où la performance est primordiale. Nous sommes maintenant mieux équipés pour aborder ces situations de front.

Un exemple d’implémentation récursive ou non récursive de la traversée du DOM peut être trouvé sur le site web de Guillaume Lathoud ici. Dans cet article, Guillaume va extrêmement loin, comparant diverses mesures de performance, par exemple le nombre d’appels récursifs, la taille de la pile, le temps, etc…, en ce qui concerne les stratégies récursives concurrentes. Son article est facilement le plus complet que j’ai vu sur la récursion de queue en JavaScript jusqu’à présent, et je vous conseille vivement de le consulter. Voici un extrait de l’article dans lequel nous créons une fonction qui collecte tous les nœuds des fichiers JavaScript dans le DOM, en utilisant une approche récursive - recursiveCall(), ainsi qu’une approche récursive de queue - tailRecursiveCall(). Essayez de comprendre le code ci-dessous…

var js_file_node_list = [] ; var js_node_check = function(node) { if ((node.nodeName === '#text') && (node.textContent.indexOf('.js') > -1)) { js_file_node_list.push(node) ; } } ; // Exécute récursivement votre fonction sur chaque noeud function recursiveCall(node, myFunction) { myFunction(node) ; var childNodes = node.childNodes ; for (var i = 0 ; i < childNodes.length ; i++) { recursiveCall(childNodes[i], myFunction) ; } } // Recursion de queue function tailRecursiveCall(node, myFunction) { return (function sub(_node, _myFunction, _from_below) { if (!_from_below) { _myFunction(_node) ; if (_node.firstChild) return sub(_node.firstChild, _myFunction, false) ; } if (_node.nextSibling) return sub(_node.nextSibling, _myFunction, false) ; if (_node.parentNode) return sub(_node.parentNode, _myFunction, true) ; })(node, myFunction, false) ; }

Nous avons donc basculé nos programmes en mode strict, nous avons modifié nos fonctions récursives pour qu’elles soient en forme d’appel de queue, et nous avons même vu des exemples. La dernière partie (et pour l’instant, la plus difficile) est d’exécuter notre code ES6 dans un environnement qui peut réellement gérer l’optimisation de l’appel de queue, et c’est là que nous avons rencontré un petit problème. L’implémentation de la récursion de queue est une caractéristique du moteur d’interprétation, par exemple V8 dans Chrome, alors que la disponibilité pour exécuter notre récursion nouvellement optimisée dépend du compilateur plutôt que du langage lui-même.

La référence la plus récente sur la disponibilité des appels de queue (en plus de toutes les autres fonctionnalités de ES6) peut être trouvée ici, et au moment de la rédaction de cet article, il n’y a actuellement pas un seul navigateur qui dispose d’une implémentation. Cela ne devrait cependant pas étouffer notre intérêt pour les nouvelles fonctionnalités du langage et de l’implémentation. Si nous nous armons de la connaissance des futurs ensembles d’outils à notre disposition, nous serons d’autant mieux préparés à écrire un code propre et hautement optimisé - une caractéristique des grands programmeurs.

Il s’agit d’une fonctionnalité passionnante pour une toute nouvelle implémentation de JavaScript, et avec le temps, nous serons amenés à en faire usage un peu partout. En attendant, pour prendre de l’avance sur les autres fonctionnalités de ES6, je recommande traceur et 6to5, qui vous permettent tous deux d’écrire du code ES6 et de le transpiler en ES5 valide et utilisable.

En prime, si vous voulez voir un bel exemple de récursion dans le monde réel, recherchez-le sur Google.

Autres lectures : Outre la research de Guillaume Lathoud sur la récursion de queue, je recommande vivement de consulter l’atelier d’Aaron Frost sur JS.Next : ES6 d’Aaron Frost sur FrontEndMasters.com. Il fournit une excellente introduction aux nombreuses fonctionnalités d’ECMAScript 6, et c’est principalement ce qui m’a incité à écrire cet article.

Chris Amatangelo est ingénieur Web chez DOOR3. Contactez-nous dès aujourd’hui