ES6 - Von der Rekursion zur Tail-Rekursion

Die nächste Version von JavaScript (ECMAScript 6) wird eine unglaublich leistungsfähige Programmierfunktion namens Tail Recursion einführen, eine Funktion, auf die ich sehr gespannt bin. In diesem Artikel möchte ich ein wenig über Rekursion vs. Iteration, Tail-Rekursion und was das für die Zukunft von JavaScript bedeutet, sprechen.

Rekursion

Die Rekursion war schon immer eine mächtige Funktion in JavaScript und vielen anderen Programmiersprachen, um Probleme zu lösen, indem man Dinge in einfachere/kleinere Versionen von sich selbst zerlegt. Im Programmierkontext kann man sich das als eine Funktion vorstellen, die sich selbst aufruft, aber mit veränderten oder reduzierten Argumenten. Die rekursive Strategie der Problemlösung führt oft zu recht eleganten Ergebnissen, mit Code, der im Vergleich zu anderen Ansätzen, wie z. B. Brute-Forcing oder Iteration, besser lesbar und klarer ist. Wenn die Aufgabe jedoch darin besteht, große Mengen verschachtelter Daten zu durchforsten, müssen wir eine Entscheidung treffen: Rekursion oder Iteration? Fangen wir mit etwas Code an…

Im Folgenden sehen Sie eine faktorielle Funktion, das typische Beispiel für eine Rekursion, das in vielen Programmiersprachen verwendet wird - nichts allzu Verrücktes oder Aufregendes.

function faktoriell(n) { return n === 1 ? 1 : n * faktoriell(n - 1); }

Um die Funktion zu erklären, nimmt factorial() einfach ein numerisches Argument, z.B. 6, und multipliziert das Argument mit der Fakultät des Arguments abzüglich 1, die dann wiederum das Argument nimmt und es mit der Fakultät von 1 multipliziert, usw., bis das Argument 1 ist und die Funktion zurückkehrt - und schon haben Sie eine Rekursion.

Die Rückgabe von 1 bezeichnet die Abschlussbedingung (oder den Basisfall), die eine rekursive Funktion benötigt, während der Rest der Funktion weiterhin ausgeführt wird und sich selbst rekursiv aufruft, bis der Basisfall erfüllt ist. Während diese einfache faktorielle Funktion aus der Perspektive der Sauberkeit gut und elegant aussieht, gibt es einige sehr große Auswirkungen, die sich hinter den Kulissen abspielen, wie wir unseren faktoriellen Aufruf ausgeführt haben. Ein guter Weg, um zu verstehen, wie factorial() seine Ausführung durchführt, ist die Visualisierung des Stapels, der erzeugt wird.

Unten sehen Sie eine grobe Darstellung dessen, was mehr oder weniger hinter den Kulissen passiert, wenn Sie eine rekursive Funktion in aktuellen Implementierungen von JavaScript ausführen.

faktoriell(6) // Speicher zuweisen und Zustand sichern 6 * faktoriell(5) // Speicher zuweisen und Zustand sichern 6 * (5 * faktoriell(4)) // Speicher zuweisen… 6 * (5 * (4 * Fakultät(3))) // Speicher zuweisen… 6 * (5 * (4 * (3 * Fakultät(2)))) // Speicherplatz zuweisen… 6 * (5 * (4 * (3 * (2 * Fakultät(1))))) // allocate mem… 6 * (5 * (4 * (3 * (2 * (1 * faktoriell(0)))))) // allocate mem… (max depth) 6 * (5 * (4 * (3 * (2 * (1 * 1))))) 6 * (5 * (4 * (3 * (2 * 1)))) 6 * (5 * (4 * (3 * 2))) 6 * (5 * (4 * 6)) 6 * (5 * 24) 6 * 120 720`

Zunächst müssen wir uns ein Bild davon machen, wie dies berechnet wird, um den Platzbedarf und die Komplexität des Speicherverbrauchs zu verstehen. Oben haben wir diesen rekursiven, kaskadierenden Baum, bei dem jeder Funktionsaufruf in den Speicher gestapelt wird, um für die Verwendung im nächsten rekursiven Aufruf zugewiesen zu werden. Jede Rekursion benötigt Speicherplatz, da wir mit dem Aufruf von faktoriell(6) zeitlich verschobene Operationen aufbauen, die schließlich nach dem letzten rekursiven Aufruf ausgeführt werden sollen. Der zugewiesene Speicherplatz steigt und fällt, so dass wir für factorial(n) n Plätze auf dem Stack belegen. Eine grafische Darstellung dieses Speicherverbrauchs im Verhältnis zur Größe des rekursiven Aufrufs könnte etwa so aussehen wie das folgende Diagramm.

Aus diesem Diagramm können wir ablesen, dass der Speicherverbrauch unbegrenzt ist (was nicht gut ist). Beachten Sie, wie der Speicherverbrauch mit jedem weiteren rekursiven Aufruf zunimmt. Letztendlich wird dieses unbegrenzte Anwachsen des Speichers unsere Fähigkeit zur Ausführung zunichte machen, da wir den Stapel aufblähen, was als Stapelüberlauf bezeichnet wird. Das Ausmaß der Rekursionsfähigkeit hängt von den Implementierungen der Browser-Engines und der jeweiligen Größe des Aufrufstapels ab. Eine Möglichkeit, einen Einblick in die verschiedenen Browser-Implementierungen zu bekommen, besteht darin, einen rekursiven Aufruf in ein Try-Catch zu verpacken, um so das Limit abzufangen und die Ausführung aufrechtzuerhalten (siehe unten).

function count(num) { try { return count((num || 0) + 1); } catch(e) { return num; } }

Diese Funktion rekursiert so lange, bis die Größe des Aufrufstapels den Speicherplatz übersteigt, so dass wir eine Schätzung der Größe des Aufrufstapels der jeweiligen Umgebung erhalten. Probieren Sie es in verschiedenen Browsern aus, um die jeweiligen Grenzen zu vergleichen.

Iteration

Die obigen Informationen lassen vermuten, dass die Verwendung von Rekursion in JavaScript als unpraktisch angesehen werden könnte (abhängig von der benötigten Call-Stack-Größe), denn jeder Algorithmus, der damit implementiert werden kann, kann auch mit Iteration implementiert werden. Schauen wir uns ein Beispiel für die Berechnung der Fakultät einer Zahl durch Iteration versus Rekursion an.

// via Iteration function factorial(n) { if (n === 0) { return 1; } else { var sum = 1; for (var i = 1; i <= n; i++) { sum = sum * i; } return sum; } }

Die obige Version ist meiner Meinung nach weniger elegant und lesbar als die zuvor deklarierte rekursive Version. Sie nutzt auch nicht ganz den funktionalen Aspekt von JavaScript, der oft als einer der, wenn nicht der beste Teil der Sprache angesehen wird. Eine iterative Schleifenlösung für das faktorielle Problem würde jedoch das Hinzufügen von Elementen zum Aufrufstapel verhindern und somit zu einem begrenzten Speicherverbrauch führen.

Wie auch immer, wir werden so tun, als seien Schleifen hässlich, und uns daran erinnern, wie sehr wir eleganten, sauberen und lesbaren Code lieben, also lassen Sie uns zu diesem glatten rekursiven Stil zurückkehren. Kein Problem, das bedeutet, dass ES6 mit dieser großartigen neuen Funktion namens Tail-Rekursion die Rettung bringt - aber zunächst einmal, was genau ist Tail-Rekursion?

Tail-Rekursion Rekursion

Was also ist Tail-Rekursion? Anstatt die rekursive Funktion als Rückgabeanweisung aufzurufen (d. h. eine neue Version ihrer selbst aufzurufen), wird ein Sprung durchgeführt und derselbe Kontext (oder Aktivierungssatz) des vorherigen rekursiven Aufrufs wiederverwendet, d. h. es entstehen keine zusätzlichen Speicherkosten. Das bedeutet, dass der Speicherverbrauch bei Verwendung der Tail-Rekursion in unseren rekursiven Funktionen konstant bleibt und nicht mit jedem rekursiven Aufruf weiter ansteigt. Bei einer ordnungsgemäß implementierten Tail-Rekursion-Version der Fakultät könnte der Speicherverbrauch beispielsweise folgendermaßen aussehen.

Vergleichen Sie das mit dem obigen Diagramm, und wir sind plötzlich viel glücklichere Programmierer. Anstatt weitere Aufrufe zum Stack hinzuzufügen und Speicher zu verbrauchen, werden frühere Stacks und Kontexte freigegeben (oder wiederverwendet) und in den Müll geworfen, wodurch ein kontinuierliches Anwachsen des Speicherverbrauchs verhindert wird. Alles ist also großartig und die Tail-Rekursion kommt, um den Tag zu retten (sozusagen). Bevor wir uns zu sehr freuen, müssen wir noch einige Vorbehalte anbringen. Um eine korrekte Tail-Rekursion durchzuführen, müssen wir drei Dinge erfüllen.

• im Strict-Modus sein

• unsere Programme in der richtigen Tail-Call-Form schreiben

• in einer Tail-Call-optimierten (TCO) Umgebung arbeiten

Die erste dieser Aufgaben ist einfach. Wenn Sie mehr über den Strict Mode erfahren möchten, sehen Sie sich die MDN-Ressourcen hier an. Ich empfehle allen JavaScript-Entwicklern, ihn zu verwenden.

Die zweite Aufgabe, nämlich die richtige Form des Schwanzaufrufs, ist etwas schwieriger. Leider würde sich unsere zuvor deklarierte elegante rekursive faktorielle Funktion selbst in einer für Tail-Calls optimierten Umgebung nicht für eine Tail-Rekursion qualifizieren. Sie ist nicht in der richtigen Tail-Call-Form, lassen Sie mich erklären…

Ein echter Tail-Call liegt vor, wenn das letzte, was eine Funktion tut, das Ergebnis des Aufrufs einer anderen Funktion ist. In der obigen Funktion gibt das hervorgehobene ternäre else das Ergebnis von n * factorial(n - 1) zurück, mit anderen Worten, es ist keine eigenständige Funktion, und folglich müsste der Stack erhalten bleiben. Ein Beispiel für eine faktorielle Funktion mit korrekten Tail-Calls (siehe unten). Beachten Sie, dass das ternäre else recur(n - 1, n * acc) als eigenständigen Aufruf zurückgibt. Beachten Sie, dass diese Version einer rekursiven faktoriellen Funktion mit korrektem Endaufruf etwas komplizierter ist, jedoch für TCO in Frage kommt und uns somit die Möglichkeiten der Endrekursion bietet.

// via Tail-Rekursion function factorial(n) { function recur(n, acc) { return n == 0 ? acc : recur(n-1, n*acc); } return recur(n, 1); }

Der Übersichtlichkeit halber hier ein stark vereinfachtes Beispiel einer nicht rekursiven Funktion in der richtigen Tail-Call-Form. Die nachstehende Funktion bietet die Möglichkeit der Tail-Call-Optimierung. Sobald foo() bar() als letzte Aktion ausführt, kann bar() den von foo() zugewiesenen Stack wiederverwenden, anstatt einen neuen hinzuzufügen (und den Speicherverbrauch zu erhöhen).

function foo() // tu etwas... return bar(); // korrekte Tail-Call-Form }

Wenn wir unsere neu gefundenen rekursiven Speicheroptimierungen in der “realen Welt” anwenden, könnten wir erhebliche Leistungsvorteile beim Durchlaufen/Verarbeiten extrem großer Datenmengen feststellen. Für die meisten von uns wird das alltägliche JavaScript, das wir schreiben, nicht unbedingt von diesen optimierten Tail Calls profitieren. Nehmen wir jedoch an, wir haben ein spezifisches Problem vor uns, das die Durchquerung eines riesigen Datenbaums erfordert. Ein Datenbaum, bei dem jeder Knoten eine beträchtliche Menge an Informationen und Overhead mit sich bringt - kommt Ihnen das bekannt vor? Natürlich tut es das, es ist die wunderbare API, die wir alle kennen und lieben, das DOM! Als Entwickler müssen wir für unsere Programme, unsere Chefs und unsere Kunden oft mit dem DOM interagieren (z. B. mit einem Algorithmus zur Durchquerung von Bäumen), bei dem die Leistung an erster Stelle steht. Nun sind wir besser gerüstet, um diese Situationen zu meistern.

Ein Beispiel für rekursive vs. tail-rekursive Implementierungen von DOM-Traversal finden Sie auf der Website von Guillaume Lathoud hier. In dem Artikel geht Guillaume extrem in die Tiefe und vergleicht verschiedene Leistungskennzahlen, z. B. die Anzahl der rekursiven Aufrufe, die Stack-Größe, die Zeit, usw., in Bezug auf konkurrierende rekursive Strategien. Sein Artikel ist mit Abstand die gründlichste Abhandlung, die ich bisher über JavaScript Tail-Rekursion gesehen habe, und ich empfehle dringend, ihn zu lesen. Unten ist ein Schnipsel aus dem Artikel, wo wir eine Funktion, die alle JavaScript-Dateien Knoten im DOM sammelt, unter Verwendung einer rekursiven Ansatz - recursiveCall(), als auch ein Schwanz rekursiven Ansatz - tailRecursiveCall(). Versuchen Sie, den folgenden Code zu verstehen…

var js_file_node_list = []; var js_node_check = function(node) { if ((node.nodeName === '#text') && (node.textContent.indexOf('.js') > -1)) { js_file_node_list.push(node); } }; // Rekursiv führt Ihre Funktion auf jedem Knoten aus function recursiveCall(node, myFunction) { myFunction(node); var childNodes = node.childNodes; for (var i = 0; i < childNodes.length; i++) { recursiveCall(childNodes[i], myFunction); } } // Tail Rekursion function tailRecursiveCall(node, myFunction) { return (function sub(_node, _myFunction, _from_below) { if (!_from_below) { _myFunction(_node); if (_node.firstChild) return sub(_node.firstChild, _myFunction, false); } if (_node.nextSibling) return sub(_node.nextSibling, _myFunction, false); if (_node.parentNode) return sub(_node.parentNode, _myFunction, true); })(node, myFunction, false); }

Wir haben also unsere Programme auf den Strict-Modus umgestellt, wir haben unsere rekursiven Funktionen so angepasst, dass sie in der richtigen Tail-Call-Form sind, und wir haben sogar Beispiele gesehen. Der letzte (und im Moment schwierigste) Teil besteht darin, unseren ES6-Code in einer Umgebung auszuführen, die die Tail-Call-Optimierung tatsächlich handhaben kann, und genau hier stoßen wir auf ein kleines Problem. Die Implementierung der Tail-Rekursion ist eine Funktion der interpretierenden Engine, z. B. V8 in Chrome, während die Verfügbarkeit zur Ausführung unserer neu optimierten Rekursion eher vom Compiler als von der Sprache selbst abhängt.

Die aktuellste Referenz für die Verfügbarkeit von Schwanzaufrufen (zusätzlich zu allen anderen ES6-Funktionen) finden Sie hier, und zum Zeitpunkt der Erstellung dieses Artikels gibt es derzeit keinen einzigen Browser, der eine Implementierung hat. Dies sollte uns jedoch nicht davon abhalten, uns für neue Sprach-/Implementierungsfunktionen zu interessieren. Wenn wir uns mit dem Wissen über die uns bald zur Verfügung stehenden Toolsets wappnen, sind wir umso besser darauf vorbereitet, sauberen, hoch optimierten Code zu schreiben - eine Eigenschaft, die einen guten Programmierer auszeichnet.

Dies ist eine aufregende Funktion für eine völlig neue JavaScript-Implementierung, und mit der Zeit werden wir überall auf sie zurückgreifen können. In der Zwischenzeit empfehle ich traceur und 6to5, die es ermöglichen, ES6-Code zu schreiben und ihn in gültiges, brauchbares ES5 zu transpilieren, um einen Vorsprung vor anderen Funktionen von ES6 zu bekommen.

Bonus: Wenn Sie ein schönes Beispiel für Rekursion in der Praxis sehen wollen, googeln Sie es.

*Zusätzliche Lektüre: Abgesehen von Guillaume Lathouds research über Tail-Rekursion empfehle ich dringend, Aaron Frosts JS.Next: ES6 Workshop auf FrontEndMasters.com. Er bietet einen großartigen einführenden Überblick über die zahlreichen Funktionen von ECMAScript 6 und hat mich in erster Linie dazu inspiriert, diesen Artikel zu schreiben

Chris Amatangelo ist ein Webingenieur bei DOOR3. Kontaktieren Sie uns noch heute!