partage de code d'optimisation de récursion de queue js

Lors de l'apprentissage des structures de données et des algorithmes, nous savons tous que toute récursion peut être optimisée en pile + boucle. Pour des fonctions récursives spécifiques, nous les optimisons généralement manuellement.

Quand j'apprenais Scala, je suis entré en contact avec le concept de récursivité de queue. Tant que nous écrivons la récursion sous forme de récursion de queue, le compilateur nous aidera automatiquement à optimiser.
ps : Toutes les récursions ne peuvent pas être réécrites en tant que récursivité de queue
En js, la récursivité de queue est généralement optimisée par l'interprète. Cependant, tous les interpréteurs JavaScript ne prennent pas en charge l'optimisation de la récursion de queue.
Pour les environnements qui ne prennent pas en charge l'optimisation de la récursion de queue, nous devons optimiser manuellement la récursivité dans une pile + boucle.
Une méthode générale est implémentée ici pour optimiser la récursivité de la queue en pile + boucle.
Le code est extrait du livre "Introduction à ECMAScript" de Ruan Yifeng.
Le code spécifique est le suivant

<span style="font-family: 微软雅黑, "Microsoft YaHei";">function tco(f) {<br/>    var value;    var active = false;    var accumulated = [];    return function accumulator() {<br/>        accumulated.push(arguments);        if(!active) {<br/>            active = true;            while(accumulated.length) {<br/>                value = f.apply(this, accumulated.shift());<br/>            }<br/>            active = false;            return value;<br/>        }<br/>    };<br/>}var sum = tco(function(x, y) {<br/>    if(y > 0) {        return sum(x + 1, y - 1);<br/>    } else {        return x;<br/>    }<br/>});let res = sum(1, 5)<br/>console.info(res);<br/></span>

Ce code est très subtil !

Analyse
On sait que toute récursion peut être écrite sous forme de boucle + pile.
Implémentez l'idée de convertir toute récursion de queue en exécution de boucle + pile sans écrire de version d'implémentation pour chaque fonction récursive de queue.
La difficulté réside dans toute implémentation générique et récursive. Plutôt que de cibler une certaine fonction récursive.
Points clés :

• Les données enregistrées dans la pile sont exactement les paramètres de la fonction récursive.

• Pour une implémentation générale, vous devez vous fier à la fonction récursive d'origine. La condition de fin de boucle est exactement la condition de fin de la récursion.

• Pour pousser les paramètres de la fonction récursive sur la pile sans modifier la fonction récursive d'origine, vous devez utiliser une fonction au lieu que la fonction récursive soit appelée pour obtenir la fonction d'entrée ginseng.

• La condition de terminaison de la fonction récursive est différente pour chaque fonction récursive, mais si la fonction récursive n'est pas appelée à nouveau, cela signifie que la condition de terminaison a été atteint. Autrement dit, la condition de terminaison est liée à l’appel de la fonction récursive. Chaque fois qu'une fonction récursive est appelée, les paramètres sont placés sur la pile. Par conséquent, vous pouvez déduire si la condition de terminaison est atteinte en fonction de la présence ou non d'éléments dans la pile.

Recommandations associées :

Introduction détaillée à la pile d'appels JavaScript, à la récursivité de queue et à l'optimisation manuelle

Cours recommandés sur la récursion de queue

Explication détaillée sur l'utilisation du tutoriel tail recursion_PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!