Dieser Artikel führt hauptsächlich die detaillierte Erklärung von JavaScript Call Stack, TailRekursion und manueller Optimierung ein. Interessierte Freunde können darauf verweisen
Call Stack (Call Stack)
Call Stack ist ein grundlegendes Computerkonzept. Hier stellen wir ein Konzept vor: Stack Frame.
Stapelrahmen bezieht sich auf den Teil des Stapelspeichers, der separat für einen Funktionsaufruf zugewiesen wird.
Wenn das laufende Programm eine andere Funktion aus der aktuellen Funktion aufruft, wird ein neuer Stapelrahmen für die nächste Funktion erstellt und dieser Stapelrahmen wird als aktueller Rahmen bezeichnet. Die ursprüngliche Funktion verfügt auch über einen entsprechenden Stapelrahmen, der als Aufrufrahmen bezeichnet wird. Jeder Stapelrahmen speichert die lokale Variable der aktuellen Funktion.
Wenn eine Funktion aufgerufen wird, wird sie oben im Aufrufstapel hinzugefügt. Nach Abschluss der Ausführung wird die Funktion oben entfernt der Aufrufstapel. Geben Sie dem Programm zu diesem Zeitpunkt die Ausführungsrechte (Rahmenzeiger) für den Stapelrahmen oben im Stapel. Diese Last-In-Last-Out-Struktur ist der Aufrufstapel der Funktion.
In JavaScript können Sie den Aufrufrahmen der aktuellen Funktion einfach über die Methode console.trace()
Tail anzeigen call
Bevor Sie über Tail-Rekursion sprechen, müssen Sie zunächst verstehen, was Tail-Call ist. Einfach ausgedrückt besteht der letzte Schritt einer Funktionsausführung darin, eine andere Funktion aufzurufen und zurückzugeben.
Das Folgende ist die korrekte Demonstration:
// 尾调用正确示范1.0
function f(x){
return g(x);
}
// 尾调用正确示范2.0
function f(x) {
if (x > 0) {
return m(x)
}
return n(x);
}Der letzte Schritt des 1.0-Programms besteht darin, die Funktion g auszuführen und gleichzeitig ihren Rückgabewert zurückzugeben. In 2.0 muss der Tail-Call nicht in die letzte -Zeile geschrieben werden, solange es sich bei der Ausführung um den letzten Schritt handelt.
Das Folgende ist ein Fehlerbeispiel:// 尾调用错误示范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
}Tail-Call-Optimierung
Im Call-Stack-Teil wissen wir, dass, wenn eine Funktion A eine andere Funktion B aufruft, ein Stack-Frame gebildet wird. Im Call-Stack gibt es beides Rufen Sie Frame A und den aktuellen Frame B auf. Dies liegt daran, dass nach Abschluss der Ausführung von Funktion B das Ausführungsrecht an A zurückgegeben werden muss. Anschließend müssen die Variablen in Funktion A, der Ort, an dem Funktion B aufgerufen wird, und andere Informationen angezeigt werden im Aufrufrahmen A gespeichert werden. Andernfalls geht alles schief, wenn Funktion B die Ausführung beendet und Funktion A weiterhin ausführt.function f() {
let m = 1;
let n = 2;
return g(m + n);
}
f();
// 等同于
function f() {
return g(3);
}
f();
// 等同于
g(3);löschen und nur die Aufrufaufzeichnung von g(3) behalten.
. Daher kann nicht gesagt werden, dass der Wert der Variablen in f gespeichert werden muss. Wenn im Allgemeinen alle Funktionsaufrufe Tail-Aufrufe sind, ist die Länge des Aufrufstapels viel kleiner und der erforderliche Speicher wird erheblich reduziert. Das bedeutet Tail-Call-Optimierung.
EndrekursionRekursion bezieht sich auf eine Methode zur Verwendung der Funktion
selbst in der Definition der Funktion. Eine Funktion, die sich selbst aufruft, wird Rekursion genannt, und eine Funktion, die sich am Ende selbst aufruft, wird Endrekursion genannt.Diese Schreibweise ist einfach und grob, weist jedoch ein sehr ernstes Problem auf. Der Aufrufstapel wächst linear mit der Zunahme von n. Wenn n eine große Zahl ist (ich habe es getestet, wenn n 100 ist, friert das Browserfenster ein ...), platzt der Stapel (Stapelüberlauf), Stapel
Überlauffunction 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.
意思就是人家已经做好了，但是就是还不能不给你用：）嗨呀，好气喔。
当然，人家肯定是有他的正当理由的：
在引擎层面消除尾递归是一个隐式的行为，程序员写代码时可能意识不到自己写了死循环的尾递归，而出现死循环后又不会报出stack overflow的错误，难以辨别。
堆栈信息会在优化的过程中丢失，开发者调试非常困难。
道理我都懂，但是不信邪的我拿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时实际执行的是这个函数。这种方法可以不用修改原递归函数，当调用递归时只用使用该方法转置一下便可解决递归调用的问题。
总结
尾递归优化是个好东西，但既然暂时用不上，那我们就该在平时编码的过程中，对使用到了递归的地方特别敏感，时刻避免出现死循环，爆栈等危险。毕竟，好的工具不如好的习惯。
Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in den JavaScript-Aufrufstapel, die Tail-Rekursion und die manuelle Optimierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
