Analyse zur Verhinderung rekursiver Stapelüberlauffehler in JavaScript

Er ist wirklich eine Figur auf Gott-Niveau und muss demütig verehrt werden

Schwanzrekursion

Eine Funktion, die sich selbst aufruft, wird Rekursion genannt. Wenn sich der Schwanz selbst aufruft, spricht man von einer Schwanzrekursion.

Rekursion ist sehr speicherintensiv, da Tausende oder Hunderte von Aufrufrahmen gleichzeitig gespeichert werden müssen und es leicht zu „Stapelüberlauf“-Fehlern kommen kann. Bei der Tail-Rekursion tritt jedoch nie ein „Stapelüberlauf“-Fehler auf, da es nur einen Aufrufrahmen gibt.

Beispiel 1

function factorial(n) {
  if (n === 1) return 1;  return n * factorial(n - 1);
}

factorial(5) // 120

Der obige Code ist eine Fakultätsfunktion. Um die Fakultät von n zu berechnen, müssen bis zu n Anrufdatensätze gespeichert werden, und die Komplexität beträgt O(n). .

Wenn als Schwanzrekursion umgeschrieben, wird nur ein Anrufdatensatz gespeichert, die Komplexität beträgt O(1)

function factorial(n, total) {
  if (n === 1) return total;  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

Beispiel 2

Es gibt ein weiteres berühmtes Beispiel Die Berechnung der Fibonacci-Folge kann auch die Bedeutung der rekursiven Schwanzoptimierung vollständig veranschaulichen.

Die rekursive Fibonacci-Folge ohne Schwanz wird wie folgt implementiert.

function Fibonacci (n) {
  if ( n <= 1 ) {return 1};  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89Fibonacci(100) // 堆栈溢出, 亲测页面直接卡死, cpu: i7-4720Fibonacci(500) // 堆栈溢出

Nach der Optimierung

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 573147844013817200000Fibonacci2(1000) // 7.0330367711422765e+208 非一般的速度Fibonacci2(10000) // Infinity

Tail-Rekursionsoptimierung

Tail-Rekursionsoptimierung wird nur im strikten Modus wirksam, dann im normalen Modus oder in solchen, die dies nicht unterstützen Feature Gibt es in dieser Umgebung eine Möglichkeit, auch die Tail-Rekursionsoptimierung zu verwenden? Die Antwort lautet: Ja, implementieren Sie einfach die Tail-Rekursionsoptimierung selbst.

Das Prinzip ist sehr einfach. Der Grund, warum die Schwanzrekursion optimiert werden muss, besteht darin, dass zu viele Aufrufstapel vorhanden sind, was zu einem Überlauf führt. Solange der Aufrufstapel reduziert wird, tritt kein Überlauf auf. Was kann getan werden, um den Aufrufstapel zu reduzieren? Verwenden Sie einfach „Schleife“ anstelle von „Rekursion“.

Das Folgende ist eine normale rekursive Funktion.

function sum(x, y) {
  if (y > 0) {    return sum(x + 1, y - 1);
  } else {    return x;
  }
}sum(1, 100000)// Uncaught RangeError: Maximum call stack size exceeded(…)

Im obigen Code ist sum eine rekursive Funktion, der Parameter x ist der Wert, der akkumuliert werden muss, und der Parameter y steuert die Anzahl der Rekursionen. Sobald die Summe so angegeben ist, dass sie 100.000 Mal rekursiv ausgeführt wird, wird ein Fehler gemeldet, der darauf hinweist, dass die maximale Anzahl von Aufrufstapeln überschritten wurde.

Die Trampolinfunktion kann eine rekursive Ausführung in eine zyklische Ausführung umwandeln.

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

Das Obige ist eine Implementierung der Trampolinfunktion, die eine Funktion f als Parameter akzeptiert. Solange f nach der Ausführung eine Funktion zurückgibt, wird die Ausführung fortgesetzt. Beachten Sie, dass wir hier eine Funktion zurückgeben und dann die Funktion ausführen, anstatt die Funktion innerhalb der Funktion aufzurufen. Dadurch wird eine rekursive Ausführung vermieden und das Problem eines zu großen Aufrufstapels beseitigt.

Dann müssen Sie nur noch die ursprüngliche rekursive Funktion neu schreiben, um bei jedem Schritt eine andere Funktion zurückzugeben.

function sum(x, y) {
  if (y > 0) {    return sum.bind(null, x + 1, y - 1);
  } else {    return x;
  }
}

Im obigen Code gibt jede Ausführung der Summenfunktion eine andere Version von sich selbst zurück.

Wenn Sie nun die Trampolinfunktion zum Ausführen von sum verwenden, tritt kein Aufrufstapelüberlauf auf.

trampoline(sum(1, 100000))// 100001

Die Trampolinfunktion ist keine echte rekursive Schwanzoptimierung, die folgende Implementierung ist .

Hier kommt der wichtige Punkt, Veteranen

function tco(f) {
  var value;  var active = false;  var accumulated = [];  return function accumulator() {
    accumulated.push(arguments);//每次将参数传入. 例如, 1 100000
    if (!active) {
      active = true;      
      while (accumulated.length) {//出循环条件, 当最后一次返回一个数字而不是一个函数时, accmulated已经被shift(), 所以出循环
        value = f.apply(this, accumulated.shift());//调用累加函数, 传入每次更改后的参数, 并执行
      }
      active = false;      
      return value;
    }
  };
}var sum = tco(function(x, y) {
  if (y > 0) {    
  return sum(x + 1, y - 1)//重点在这里, 每次递归返回真正函数其实还是accumulator函数
  }  
  else {    
  return x
  }
});

sum(1, 100000);//实际上现在sum函数就是accumulator函数// 100001

Im obigen Code ist die TCO-Funktion die Implementierung der rekursiven Schwanzoptimierung, und ihr Geheimnis liegt in der aktiven Zustandsvariablen. Standardmäßig ist diese Variable inaktiv. Sobald der rekursive Endoptimierungsprozess eingegeben wird, wird diese Variable aktiviert. Dann gibt jede Runde der rekursiven Summe undefiniert zurück, sodass eine rekursive Ausführung vermieden wird und das akkumulierte Array die Parameter jeder Runde der Summenausführung speichert und immer wertvoll ist, was sicherstellt, dass die while-Schleife innerhalb der Akkumulatorfunktion immer ausgeführt wird. Auf diese Weise wird „Rekursion“ geschickt in „Schleife“ geändert, und die Parameter der nächsten Runde ersetzen die Parameter der vorherigen Runde, wodurch sichergestellt wird, dass es nur eine Ebene im Aufrufstapel gibt.

Das obige ist der detaillierte Inhalt vonAnalyse zur Verhinderung rekursiver Stapelüberlauffehler in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!