Teilen von Code zur Optimierung der js-Tail-Rekursion

Beim Erlernen von Datenstrukturen und Algorithmen wissen wir alle, dass alle Rekursionen in Stapel + Schleife optimiert werden können. Für bestimmte rekursive Funktionen optimieren wir sie im Allgemeinen manuell.

Als ich Scala lernte, kam ich mit dem Konzept der Schwanzrekursion in Kontakt. Solange wir die Rekursion als Schwanzrekursion schreiben, hilft uns der Compiler automatisch bei der Optimierung.
ps: Nicht jede Rekursion kann als Tail-Rekursion umgeschrieben werden
In js wird die Tail-Rekursion normalerweise vom Interpreter optimiert. Allerdings unterstützen nicht alle JavaScript-Interpreter die Schwanzrekursionsoptimierung.
Für Umgebungen, die die Endrekursionsoptimierung nicht unterstützen, müssen wir die Rekursion manuell in einen Stapel + Schleife optimieren.
Hier wird eine allgemeine Methode implementiert, um die Tail-Rekursion in Stack + Loop zu optimieren.
Der Code ist ein Auszug aus dem Buch „Introduction to ECMAScript“ von Ruan Yifeng.
Der spezifische Code lautet wie folgt

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

Dieser Code ist sehr subtil!

Analyse
Es ist bekannt, dass jede Rekursion als Schleife + Stapel geschrieben werden kann.
Implementieren Sie die Idee, jede Tail-Rekursion in eine Schleifen- und Stapelausführung umzuwandeln, ohne für jede Tail-Rekursionsfunktion eine Implementierungsversion zu schreiben.
Die Schwierigkeit liegt in jeder schwanzrekursiven, generischen Implementierung. Anstatt auf eine bestimmte rekursive Funktion abzuzielen.
Wichtige Punkte:

• Die im Stapel gespeicherten Daten sind genau die Parameter der rekursiven Funktion.

• Für die allgemeine Implementierung müssen Sie sich auf die ursprüngliche rekursive Funktion verlassen. Die Beendigungsbedingung der Schleife ist genau die Endbedingung der Rekursion.

• Um die Parameter der rekursiven Funktion auf den Stapel zu verschieben, ohne die ursprüngliche rekursive Funktion zu ändern, müssen Sie zum Abrufen eine Funktion anstelle der aufgerufenen rekursiven Funktion verwenden die Funktionseingabe Ginseng.

• Die Beendigungsbedingung der rekursiven Funktion ist für jede rekursive Funktion unterschiedlich. Wenn die rekursive Funktion jedoch nicht erneut aufgerufen wird, bedeutet dies, dass die Beendigungsbedingung erfüllt ist erreicht. Das heißt, die Beendigungsbedingung hängt mit dem Aufruf der rekursiven Funktion zusammen. Bei jedem Aufruf einer rekursiven Funktion werden Parameter auf den Stapel gelegt. Daher können Sie basierend darauf, ob Elemente im Stapel vorhanden sind, ableiten, ob die Beendigungsbedingung erreicht ist.

Verwandte Empfehlungen:

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

Empfohlene Kurse zur Tail-Rekursion

Detaillierte Erklärung zur Verwendung der Tail-Rekursion_PHP-Tutorial

Das obige ist der detaillierte Inhalt vonTeilen von Code zur Optimierung der js-Tail-Rekursion. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!