Detaillierte Einführung in den JavaScript-Aufrufstapel, die Tail-Rekursion und die manuelle Optimierung

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
}

1.0 Der letzte Schritt ist eine Zuweisungsoperation, 2.0 der letzte Schritt ist eine Additionsoperation, 3.0 hat implizit eine undefinierte Rückgabe

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.

Jetzt fügen wir Funktion B in den letzten Aufruf von Funktion A ein (d. h. den Endaufruf). Ist es notwendig, den Stapelrahmen von Funktion A beizubehalten? Natürlich nicht, da der Aufrufort und die internen Variablen nicht erneut verwendet werden. Ersetzen Sie daher einfach den Stapelrahmen von Funktion A durch den Stapelrahmen von Funktion B. Wenn die innere Funktion natürlich Variablen der äußeren Funktion verwendet, muss der Stapelrahmen von Funktion A weiterhin beibehalten werden. Ein typisches Beispiel ist ein Abschluss.

Es gibt viele Blogartikel im Internet über die Erklärung von Tail Calls, und einer der am weitesten verbreiteten Artikel hat diesen Absatz. Ich stimme nicht ganz zu.

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

Das Folgende ist der Originaltext des Blogs: Wenn Funktion g im obigen Code kein Tail-Call ist, muss Funktion f die Werte der internen Variablen m und n speichern Anrufstandort von g und andere Informationen. Da die Funktion f jedoch nach dem Aufruf von g endet, können Sie im letzten Schritt der Ausführung die Aufrufaufzeichnung von f()

löschen und nur die Aufrufaufzeichnung von g(3) behalten.

Aber ich denke, die erste Methode führt auch zuerst den m+n-Schritt aus, ruft dann die Funktion g auf und kehrt gleichzeitig zurück. Dies sollte ein Rückruf sein. Gleichzeitig wird der Wert von m + n auch über Parameter an die Funktion g übergeben und bezieht sich nicht direkt auf

. 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.

Endrekursion

Rekursion 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.

Die häufigste Rekursion, die Fibonacci-Folge, die Art und Weise, eine gewöhnliche Rekursion zu schreiben:

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

Überlauf

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

). Dies liegt daran, dass bei dieser rekursiven Operation eine große Anzahl von Stapelrahmen gleichzeitig gespeichert wird, der Aufrufstapel sehr lang ist und eine große Menge an Speicher verbraucht wird.

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

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时实际执行的是这个函数。这种方法可以不用修改原递归函数，当调用递归时只用使用该方法转置一下便可解决递归调用的问题。

总结

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

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!