Optimierung der JavaScript-Schwanzrekursion

Hallo Leser.

Manchmal müssen Sie zur Lösung des Problems die Rekursion verwenden , die Vor- und Nachteile hat. Ich bin auf ein Stapelüberlaufproblem gestoßen.

Die maximale Rekursionstiefe wird durch die JavaScript-Engine begrenzt. Sie können genau mit 10.000 verschachtelten Anrufen rechnen, einige Dolmetscher erlauben mehr, aber für die meisten von ihnen liegen 100.000 Anrufe außerhalb des Funktionsumfangs. Es gibt automatische Optimierungen, die helfen, ein Überlaufen des Aufrufstapels zu vermeiden ("Tail-Rekursionsoptimierung"), aber sie werden noch nicht überall unterstützt und funktionieren nur in einfachen Fällen.

Ein Beispiel für eine rekursive Funktion:

function sum(n) { return n === 0 ? 0 : n + sum(n - 1) } sum(5) // 1 + 2 + 3 + 4 + 5 = 15 sum(100000) // Error: Maximum call stack size exceeded. 

Die Schwanzrekursion ermöglicht die Optimierung von Aufrufen durch den Compiler und ist bereits im ES6- Standard enthalten, aber die Browserunterstützung lässt zu wünschen übrig .

Ein Beispiel für eine rekursive Schwanzfunktion:

 function sum(number, s = 0){ return number === 0 ? s : sum(number - 1, s + number) } 

Ohne Browserunterstützung treten jedoch dieselben Probleme auf - der Stapelüberlauf. Wir können versuchen, zusammen mit Trampolin zu verwenden .

Wir werden einen Dekorator schreiben, der eine modifizierte rekursive Funktion (nächster Schritt) übernimmt und in einer Schleife ausführt, ohne die Aufruftiefe zu erhöhen.

 function trampoline(fn) { return function(...args) { let result = fn.apply(fn.context, args) while (typeof result === 'function') { result = result() } return result } } 

Jetzt sollte unsere rekursive Funktion eine Funktion zurückgeben, die sofort vom Dekorateur ausgeführt wird. Auf diese Weise erstellen wir bedingt ein Array von Funktionen und führen sie nacheinander aus. Da wir jedoch jedes Mal eine neue anonyme Funktion zurückgeben, arbeitet dieser Code etwas langsamer.

 function sum(number, s = 0) { return number === 0 ? s : () => sum(number - 1, s + number) } 

Wir verwenden:

 const trampolineSum = trampoline(sum) trampolineSum(100000) // 5000050000 

Dies ist mein erster Artikel. Ich habe versucht, die Konzepte nicht erneut zu erzählen, und einen Link zu den Quellen bereitgestellt. Das Thema ist nicht eindeutig und existiert seit langem auf englischsprachigen Websites. Leider habe ich es nicht auf Russisch gefunden.

Vielen Dank für Ihre Aufmerksamkeit. Einen schönen Tag noch :)

Update
Leistung:

# 1 Rekursion




# 2 Iteration




# 3 Schwanzrekursion und Trampolin




# 4 Schwanzrekursion und Trampolin (eine große Anzahl)




Den Ergebnissen zufolge sehen wir, dass unser Dekorateur zwar den Stapelüberlauffehler vermeiden kann, aber langsamer arbeitet als die rekursive und iterative Version. Daher sollte diese Methode nur verwendet werden, wenn Sie die Rekursion nicht durch Iteration ersetzen können oder Angst vor Stapelüberläufen haben, wenn Sie Ihre rekursive Funktion ausführen.