Konsole & …: Rekursion
Die Fähigkeit einer Funktion in JavaScript, sich rekursiv aufrufen zu können, scheint nichts Besonderes zu sein. Dennoch gibt es dabei ein paar Aspekte zu beachten, insbesondere im Hinblick auf die kommende Version der Sprache: ECMAScript 6.
- Golo Roden
"Konsole & Kontext" ist eine gemeinsame Serie von Golo Roden und Michael Wiedeking, in der sich die beiden regelmäßig mit Konzepten der (funktionalen) Programmierung beschäftigen. Während "Konsole & …" die praktische Anwendung dieser Konzepte in JavaScript und Node.js zeigt, erläutert "… & Kontext" deren jeweiligen eher theoretischen Hintergrund.
Auf den ersten Blick scheint das Thema der Rekursion in JavaScript einer eigenen Notiz kaum würdig zu sein. Anders als beispielsweise frühe Versionen von Fortran unterstützt JavaScript Rekursion nämlich, ohne sie jedoch als essenziell notwendiges Konstrukt zu behandeln, wie es beispielsweise Haskell vorsieht.
Dementsprechend leicht fällt es in JavaScript, eine Funktion rekursiv aufzurufen. Die Sprache erfordert weder eine spezielle Art der Funktionsdeklaration noch besonderes Augenmerk beim Aufruf. Stattdessen genügt es, eine Funktion aus sich selbst heraus aufzurufen:
var faculty = function (n) {
return n > 0
? n * faculty(n - 1)
: 1;
};
Rekursion versus Iteration
Wenngleich der Code an sich wenig bemerkenswert ist, verdient die Ausführungsgeschwindigkeit jedoch einige Aufmerksamkeit. Auf meinem MacBook Pro benötigt die rekursive Berechnung der Fakultät die ungefähr dreifache Zeit der iterativen Variante.
Das ist wenig verwunderlich, schließlich resultiert die rekursive Berechnung rasch in einer hohen Anzahl an Funktionsaufrufen. Da JavaScript für jeden einzelnen Funktionsaufruf zunächst einen Stack Frame erzeugen und ihn später wieder freigeben muss, führt das zu Aufwand, der bei einer iterativen Lösung entfällt. Außerdem läuft man bei der rekursiven Variante Gefahr, einem Stack Overflow zu begegnen: Dann nämlich, wenn der vom System vorgesehene Speicher für Stack Frames nicht ausreicht und sich daher keine weiteren Funktionen aufrufen lassen.
Dennoch weist die rekursive Variante einen gewissen Charme auf: Immerhin ist die Fakultät auch in der Mathematik rekursiv definiert, weshalb eine derartige Implementierung natürlicher wirkt als eine iterative.
Endrekursion als Lösung?
Allerdings gibt es einen Trick, um Code rekursiv schreiben, aber mit der Leistung der iterativen Variante ausführen zu können. Enthält eine Funktion als letzte Anweisung einen rekursiven Funktionsaufruf, kann die Laufzeitumgebung den Stack Frame der aufrufenden Funktion wieder verwenden: Mit Ausnahme der ursprünglichen Rücksprungadresse kann sie alle Werte bedenkenlos überschreiben und die Funktion erneut ausführen.
Dieses Vorgehen wird als Endrekursion (im Englischen Tail Call) bezeichnet und erspart den an der Stelle unnötigen Aufwand zum Erzeugen und Freigeben der diversen Stack Frames. Allerdings muss die Laufzeitumgebung das Vorgehen auch von Seiten des Compilers unterstützen: Das zugehörige Feature heißt Tail Call Optimization (TCO).
Offensichtlich weist die zuvor verwendete rekursive Variante zur Berechnung der Fakultät keine Endrekursion auf. Die letzte Anweisung vor dem return-Schlüsselwort ist nämlich kein rekursiver Funktionsaufruf, sondern eine Multiplikation:
? n * faculty(n - 1)
Der Code lässt sich jedoch leicht auf eine endrekursive Variante erweitern. Dazu bedarf es eines zusätzlichen Parameters, der als Platzhalter für den bereits berechneten Teil der Fakultät dient. Damit jedoch die Signatur der faculty-Funktion erhalten bleibt, bietet es sich an, die rekursive Berechnung in eine innere Funktion auszulagern:
var faculty = function (n) {
var recFaculty = function (n, accumulator) {
if (n === 0) {
return accumulator;
}
return recFaculty(n - 1, n * accumulator);
};
return recFaculty(n, 1);
};
Warten auf ECMAScript 6
Prinzipiell liegt damit eine auf Endrekursion optimierte Variante der Fakultätsberechnung vor, allerdings ist ihr Nutzen in der Praxis (noch) begrenzt: Wie bereits erwähnt genügt es nicht, dass der Code entsprechend vorbereitet ist, auch die Laufzeitumgebung muss TCO unterstützen.
Genau daran mangelt es derzeit, denn die Festschreibung von TCO im Sprachstandard erfolgt erst mit der noch ausstehenden Sprachversion ECMAScript 6. Die gute Nachricht ist aber, dass man sich im Vergleich zur klassischen rekursiven Variante derzeit zumindest keinen Nachteil einhandelt, für die Zukunft aber bereits bestens gerüstet ist. Daher spricht nichts dagegen, Code auch heute schon im Hinblick auf Endrekursion zu optimieren.
tl;dr: JavaScript unterstützt Rekursion, zumindest derzeit aber noch keine Endrekursion. Mit der kommenden Version ECMAScript 6 wird dies aber eingeführt, weshalb es sich bereits heute lohnt, Code im Hinblick auf Endrekursion zu optimieren. ()
