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

Cet article présente principalement l'explication détaillée de la pile d'appels JavaScript, de la queuerécursion et de l'optimisation manuelle. Il a une certaine valeur de référence. Les amis intéressés peuvent s'y référer

Call Stack (Call Stack)

Call Stack est un concept informatique de base. Nous introduisons ici un concept : le cadre de pile.

le cadre de pile fait référence à la partie de l'espace de pile allouée séparément pour un appel

de fonction .

Lorsque le programme en cours d'exécution appelle une autre fonction à partir de la fonction actuelle, un nouveau cadre de pile sera créé pour la fonction suivante et ce cadre de pile sera entré. Ce cadre de pile est appelé le cadre actuel. La fonction d'origine possède également un cadre de pile correspondant, appelé cadre d'appel. Chaque cadre de pile stockera la

variable locale de la fonction actuelle.

Lorsqu'une fonction est appelée, elle sera ajoutée en haut de la pile d'appels. Une fois l'exécution terminée, la fonction sera supprimée du haut de. la pile d’appels. Et donnez au programme les droits d'exécution (pointeur de cadre) sur le cadre de pile en haut de la pile à ce moment-là. Cette structure dernier entré, dernier sorti est la pile d’appels de la fonction.

En JavaScript, vous pouvez facilement visualiser le frame appelant de la fonction actuelle via la méthode console.trace()

Tail call

Avant de parler de récursion de queue, vous devez d'abord comprendre ce qu'est l'appel de queue. En termes simples, la dernière étape de l'exécution d'une fonction consiste à appeler une autre fonction et à revenir.

Ce qui suit est la démonstration correcte :

// 尾调用正确示范1.0
function f(x){
 return g(x);
}

// 尾调用正确示范2.0
function f(x) {
 if (x > 0) {
  return m(x)
 }
 return n(x);
}

La dernière étape du programme 1.0 consiste à exécuter la fonction g et à renvoyer sa valeur de retour en même temps. Dans la version 2.0, l'appel de queue n'a pas besoin d'être écrit dans la dernière ligne

, tant qu'il s'agit de la dernière étape lors de son exécution. Ce qui suit est un exemple d'erreur :

1.0 La dernière étape est une opération d'affectation, 2.0 la dernière étape est une opération d'addition, 3.0 a implicitement un retour non défini

// 尾调用错误示范1.0
function f(x){
 let y = g(x);
 return y;
}

// 尾调用错误示范2.0
function f(x){
 return g(x) + 1;
}
// 尾调用错误示范3.0
function f(x) {
 g(x); // 这一步相当于g(x) return undefined
}

Optimisation des appels de queue

Dans la partie pile d'appels, nous savons que lorsqu'une fonction A appelle une autre fonction B, un cadre de pile sera formé. Dans la pile d'appels, il y a les deux. appelez le cadre A et le cadre B actuel. En effet, une fois l'exécution de la fonction B terminée, le droit d'exécution doit être renvoyé à A. Ensuite, les variables à l'intérieur de la fonction A, l'emplacement où la fonction B est appelée et d'autres informations doivent être enregistré dans la trame appelante A. Sinon, lorsque la fonction B aura fini de s'exécuter et continuera d'exécuter la fonction A, tout ira mal.

Alors maintenant, nous mettons la fonction B dans le dernier appel de la fonction A (c'est-à-dire l'appel final). Est-il nécessaire de conserver le cadre de pile de la fonction A ? Bien sûr que non, car son emplacement d'appel et ses variables internes ne seront plus utilisés. Par conséquent, remplacez simplement le cadre de pile de la fonction A par le cadre de pile de la fonction B. Bien sûr, si la fonction interne utilise des variables de la fonction externe, alors le cadre de pile de la fonction A doit toujours être conservé. Un exemple typique est une fermeture.

Il existe de nombreux articles de blog sur Internet expliquant les appels de queue, et l'un des plus largement diffusés contient ce paragraphe. Je ne suis pas tout à fait d'accord.

Ce qui suit est le texte original du blog : Dans le code ci-dessus, si la fonction g n'est pas un appel de queue, la fonction f doit enregistrer les valeurs des variables internes m et n, le emplacement d'appel de g et autres informations. Mais comme la fonction f se termine après l'appel de g, donc dans la dernière étape d'exécution, vous pouvez

function f() {
 let m = 1;
 let n = 2;
 return g(m + n);
}
f();
// 等同于
function f() {
 return g(3);
}
f();
// 等同于
g(3);

supprimer

l'enregistrement d'appel de f() et conserver uniquement l'enregistrement d'appel de g(3).
Mais je pense que dans la première méthode, l'étape m+n est également effectuée en premier, puis la fonction g est appelée et renvoyée en même temps. Cela devrait être un appel de queue. Dans le même temps, la valeur de m+n est également transmise à la fonction g via des paramètres et ne fait pas directement référence à

, on ne peut donc pas dire que la valeur de la variable à l'intérieur de f doit être enregistrée.

En général, si tous les appels de fonction sont des appels de fin, la longueur de la pile d'appels sera beaucoup plus petite et la mémoire requise sera considérablement réduite. C’est ce que signifie l’optimisation des appels de queue.

Récursion de queue

La récursion fait référence à une méthode d'utilisation de la fonction elle-même dans la définition de la fonction. Une fonction qui s'appelle elle-même est appelée récursivité, et une fonction qui s'appelle à la fin est appelée récursion de queue.

La récursion la plus courante, la séquence de Fibonacci, la façon d'écrire la récursion ordinaire :

Cette façon d'écrire est simple et grossière, mais elle a un problème très sérieux. La pile d'appels augmente linéairement avec l'augmentation de n. Lorsque n est un grand nombre (je l'ai testé, quand n vaut 100, la fenêtre du navigateur se fige...), la pile va éclater (débordement de pile), pile

débordement

). En effet, dans cette opération récursive, un grand nombre de trames de pile sont enregistrées en même temps, la pile d'appels est très longue et une énorme quantité de mémoire est consommée.

function f(n) {
 if (n === 0 || n === 1) return n 
 else return f(n - 1) + f(n - 2)
}

接下来，将普通递归升级为尾递归看看。

function fTail(n, a = 0, b = 1) { 
 if (n === 0) return a
 return fTail(n - 1, b, a + b)
}

很明显，其调用栈为

代码如下:

fTail(5) => fTail(4, 1, 1) => fTail(3, 1, 2) => fTail(2, 2, 3) => fTail(1, 3, 5) => fTail(0, 5, 8) => return 5

被尾递归改写之后的调用栈永远都是更新当前的栈帧而已，这样就完全避免了爆栈的危险。

但是，想法是好的，从尾调用优化到尾递归优化的出发点也没错，然并卵：），让我们看看V8引擎官方团队的解释

Proper tail calls have been implemented but not yet shipped given that a change to the feature is currently under discussion at TC39.

意思就是人家已经做好了，但是就是还不能不给你用：）嗨呀，好气喔。

当然，人家肯定是有他的正当理由的：

1. 在引擎层面消除尾递归是一个隐式的行为，程序员写代码时可能意识不到自己写了死循环的尾递归，而出现死循环后又不会报出stack overflow的错误，难以辨别。

2. 堆栈信息会在优化的过程中丢失，开发者调试非常困难。

道理我都懂，但是不信邪的我拿nodeJs（v6.9.5）手动测试了一下：

好的，我服了

手动优化

虽然我们暂时用不上ES6的尾递归高端优化，但递归优化的本质还是为了减少调用栈，避免内存占用过多，爆栈的危险。而俗话说的好，一切能用递归写的函数，都能用循环写——尼克拉斯·夏，如果将递归改成循环的话，不就解决了这种调用栈的问题么。

方案一：直接改函数内部，循环执行

function fLoop(n, a = 0, b = 1) { 
 while (n--) {
  [a, b] = [b, a + b]
 }
 return a
}

这种方案简单粗暴，缺点就是没有递归的那种写法比较容易理解。

方案二：Trampolining（蹦床函数）

function trampoline(f) { 
 while (f && f instanceof Function) {
  f = f()
 }
 return f
}

function f(n, a = 0, b = 1) { 
 if (n > 0) {
  [a, b] = [b, a + b]
  return f.bind(null, n - 1, a, b)
 } else {
  return a
 }
}

trampoline(f(5)) // return 5

这种写法算是容易理解一些了，就是蹦床函数的作用需要仔细看看。缺点还有就是需要修改原函数内部的写法。

方案三：尾递归函数转循环方法

function tailCallOptimize(f) { 
 let value
 let active = false
 const accumulated = []
 return function accumulator() {
  accumulated.push(arguments)
  if (!active) {
   active = true
   while (accumulated.length) {
    value = f.apply(this, accumulated.shift())
   }
   active = false
   return value
  }
 }
}

const f = tailCallOptimize(function(n, a = 0, b = 1) { 
 if (n === 0) return a
 return f(n - 1, b, a + b)
})
f(5) // return 5

经过 tailCallOptimize 包装后返回的是一个新函数 accumulator，执行 f时实际执行的是这个函数。这种方法可以不用修改原递归函数，当调用递归时只用使用该方法转置一下便可解决递归调用的问题。

总结

尾递归优化是个好东西，但既然暂时用不上，那我们就该在平时编码的过程中，对使用到了递归的地方特别敏感，时刻避免出现死循环，爆栈等危险。毕竟，好的工具不如好的习惯。

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!