Endrekursion für Node.js

Inhaltsverzeichnis

Die Rekursion ist eines der grundlegenden Konzepte der Informatik. Diverse Probleme lassen sich rekursiv sehr elegant formulieren, gelegentlich stößt man mit dem Vorgehen aber auch an Grenzen. Als Ausweg bietet sich ein endrekursiver Algorithmus an. Wie funktioniert das in Node.js?

Zumindest zu Übungszwecken hat vermutlich jeder Entwickler schon einmal die Fakultät implementiert. Dabei handelt es sich um eine mathematische Funktion, deren Definition rekursiv angegeben wird:

fac(1) = 1
fac(n) = n * fac(n - 1)

Dementsprechend leicht lässt sich die Funktion in einer Programmiersprache umsetzen. Man muss lediglich die Rekursion auch im Code aufgreifen, wie das folgende Beispiel in Node.js zeigt:

'use strict';

const fac = function (n) {
  if (n === 1) {
    return 1;
  }

  return n * fac(n - 1);
};

console.log(fac(5));
// => 120

Rekursive Probleme

Allerdings stößt solcher Code rasch an seine Grenzen. Das liegt in dem Fall an dem nicht ausreichenden Wertebereich des Datentyps number, sodass bereits die Berechnung der Fakultät von 171 den Wert Infinity zurückgibt.

Es gibt jedoch noch ein zweites Problem, das typisch für rekursiven Code ist. Jeder Aufruf ist ein weiterer Funktionsaufruf, dessen Daten auf dem Stack abzulegen sind. Das betrifft Parameter, lokale Variablen, Rückgabewerte und Rücksprungadressen. Je häufiger sich eine Funktion rekursiv selbst aufruft, desto mehr Speicher im Stack wird belegt.

Das Problem dabei ist, dass dieser Speicher endlich ist. Das gilt auch für moderne Betriebssysteme, die die Größe des Stacks sogar erstaunlich niedrig ansetzen.

Eine Zeichenkette umkehren

Als Beispiel soll eine Funktion zum Umkehren einer Zeichenkette dienen, wofür JavaScript keine eingebaute Funktion kennt. Der übliche Ansatz besteht darin, die Zeichenkette in ein Array von Zeichen zu zerlegen, das Array umzukehren (dafür gibt es eine Funktion) und das Ergebnis wieder zu konkatenieren:

const reverse = function (text) {
  return text.split('').reverse().join('');
};

Zu Übungszwecken lässt sich das Problem aber auch rekursiv lösen, wie der folgende Code zeigt:

const revert = function (text) {
  if (text.length === 0) {
    return '';
  }
  const first = text[0],
        rest = text.substr(1);

  return revert(rest) + first;
};

Ruft man die Funktion mit immer größeren Eingaben auf, lässt sich rasch die Situation provozieren, in der kein Platz für weitere Funktionsaufrufe mehr im Stack vorhanden ist:

/Users/golo/Desktop/revert.js:9
        rest = text.substr(1);
                    ^
RangeError: Maximum call stack size exceeded
    at String.substr (native)
    at revert (/Users/golo/Desktop/revert.js:9:21)
    at revert (/Users/golo/Desktop/revert.js:11:10)

Endrekursion verwenden

Lösen lässt sich das Problem, indem man die Funktion geringfügig anpasst:

const revert = function (text, acc = '') {
  if (text.length === 0) {
    return acc;
  }

  const first = text[0],
        rest = text.substr(1);

  return revert(rest, first + acc);
};

Das Geheimnis dabei liegt in der jeweils letzten Anweisung der Funktion. Im ersten Fall bewirkt die Zeile

return revert(rest) + first;

zunächst einen rekursiven Aufruf der Funktion, anschließend muss sie noch eine Konkatenation der Zeichenketten ausführen. Die letzte Anweisung ist also das Zusammenfügen der Zeichenketten. Vergleicht man das mit der letzten Zeile des zweiten Beispiels, fällt auf, dass in dem Fall der rekursive Aufruf die letzte Anweisung ist:

return revert(rest, first + acc);

Möglich wird das durch die Verwendung des neuen Parameters acc, der die Zwischenergebnisse speichert. Das Zusammenfügen der Zeichenketten erfolgt in dem Fall vor dem Aufruf der Funktion, da es bereits für die Berechnung des Parameters erforderlich ist.

Voraussetzungen

Eine solche Situation nennt man Endrekursion, oder auf Englisch Tail Call Recursion. Das Besondere daran ist, dass sich eine Endrekursion vom Compiler in eine iterative Version umwandeln lässt, sodass die eigentliche Rekursion verschwindet. Das ist möglich, weil die Funktion nach der letzten Anweisung weder die Parameter noch die lokalen Variablen benötigt und daher der Bereich im Stack für den nächsten Aufruf wiederverwendet werden kann.

Mit anderen Worten: Anstatt einen vollwertigen Funktionsaufruf durchzuführen, werden lediglich die Werte im Stack verändert und die Funktion daraufhin erneut ausgeführt. Damit das funktioniert, muss die Laufzeitumgebung das Verfahren allerdings unterstützen.

In Node.js funktioniert das, wenn man zum einen den Strict-Mode verwendet, und Node.js zum anderen mit dem Kommandozeilenparameter --harmony startet.

tl;dr: Rekursive Aufrufe lassen sich von Node.js als iterativer Code ausdrücken, wenn man sie endrekursiv formuliert. Zum Ausführen ist außerdem die Angabe des zusätzlichen Kommandozeilenparameters --harmony erforderlich. ()