Rekursion

Einen Turm von Hanoi mit 64 Scheiben zu versetzen, kostet 18 446 744 073 709 551 615 Züge; eine rekursive Funktion beschreibt die Lösung in vier Zeilen.

Eine Funktion, die sich selbst aufruft

Manche Probleme enthalten eine kleinere Kopie ihrer selbst. Die Fakultät von 5, geschrieben 5!, ist 5 × 4 × 3 × 2 × 1 = 120. Schau noch einmal hin: Das ist 5 × (4 × 3 × 2 × 1), also 5 × 4!. Allgemein gilt n! = n × (n − 1)!. Um eine Fakultät zu berechnen, kannst du also eine kleinere Fakultät berechnen und multiplizieren. Eine Funktion, die ein Problem löst, indem sie sich selbst mit einer kleineren Version aufruft, ist rekursiv.

function factorial(n) {
  if (n <= 1) return 1;          // Basisfall: hier aufhören
  return n * factorial(n - 1);   // Rekursionsfall: ein kleineres Problem
}
console.log(factorial(5)); // 120

Jede rekursive Funktion braucht zwei Teile. Der Basisfall (Rekursionsanker) ist eine Eingabe, die klein genug ist, um sie direkt zu beantworten, ohne weiteren Aufruf: hier ist die Fakultät von 1 gleich 1. Der Rekursionsfall verkleinert das Problem und ruft die Funktion erneut auf. Jeder Aufruf muss dem Basisfall näherkommen. Tut er das nicht, etwa wenn du aus Versehen factorial(n + 1) schreibst, enden die Aufrufe nie.

Der Aufrufstapel

Wie behält der Computer all die unfertigen Aufrufe im Blick? Wenn factorial(5) läuft, kommt es zu 5 * factorial(4) und muss auf die Antwort warten. Der Computer legt den wartenden Aufruf auf einen Stapel (Stack), einen Haufen, bei dem das zuletzt Hingelegte zuerst wieder heruntergenommen wird. factorial(4) wartet auf factorial(3), und so weiter bis factorial(1), das sofort 1 zurückgibt. Dann wird der Stapel abgebaut: factorial(2) gibt 2 zurück, factorial(3) gibt 6 zurück, factorial(4) gibt 24 zurück und factorial(5) gibt 120 zurück.

Der Stapel hat eine begrenzte Größe. Eine Rekursion, die ihren Basisfall nie erreicht, fügt so lange Aufrufe hinzu, bis der Platz ausgeht, und JavaScript bricht mit einem Fehler ab. In Chrome und Node.js lautet die Meldung "RangeError: Maximum call stack size exceeded". Dieselbe Grenze bedeutet, dass sehr tiefe Rekursion, mit Hunderttausenden Ebenen, besser als Schleife geschrieben wird.

Die Türme von Hanoi

Die Türme von Hanoi sind ein Rätsel, das der französische Mathematiker Édouard Lucas 1883 veröffentlichte. Es gibt drei Stäbe und auf dem ersten einen Stapel unterschiedlich großer Scheiben, die größte unten. Ziel ist, den ganzen Stapel auf den dritten Stab zu bringen. Du darfst immer nur eine Scheibe bewegen, nur die oberste eines Stabs, und nie eine größere Scheibe auf eine kleinere legen.

Schritt für Schritt zu überlegen, wohin jede Scheibe kommt, wird schnell verwirrend. Rekursiv gedacht wird es kurz. Um n Scheiben von A nach C zu bringen: Bring zuerst die oberen n − 1 Scheiben aus dem Weg, von A nach B. Bring dann die größte Scheibe von A nach C. Bring dann die n − 1 Scheiben von B auf sie nach C. n − 1 Scheiben zu versetzen, ist dasselbe Rätsel, eine Nummer kleiner, und eine Scheibe zu versetzen, ist der Basisfall. Bei 3 Scheiben ergibt das 7 Züge. Das Labor zeigt bei jedem Zug den Stapel der wartenden Aufrufe.

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7 Züge

Wie viele Züge brauchen n Scheiben? n Scheiben zu versetzen, kostet zweimal n − 1 Scheiben plus einen Zug: M(n) = 2M(n − 1) + 1, mit M(1) = 1. Das ergibt 1, 3, 7, 15, 31, also M(n) = 2ⁿ − 1, und keine Lösung kommt mit weniger aus. Zehn Scheiben brauchen 1023 Züge. Vierundsechzig Scheiben brauchen 2⁶⁴ − 1 = 18 446 744 073 709 551 615 Züge. Bei einem Zug pro Sekunde sind das etwa 585 Milliarden Jahre. Das ist das O(2ⁿ)-Wachstum aus der letzten Einheit.

Rekursion, Schleifen und doppelte Arbeit

Alles, was mit Rekursion geschrieben ist, lässt sich auch mit einer Schleife und einem eigenen Stapel schreiben, und einfache Fälle wie die Fakultät sind als Schleife oft klarer. Rekursion glänzt, wenn das Problem selbst wie ein Baum geformt ist: das Teilen einer Liste bei Mergesort, das Durchsuchen von Ordnern in Ordnern oder die Suche in einem Labyrinth, um die es in der letzten Einheit geht. Eine Falle ist doppelte Arbeit. Die Fibonacci-Zahlen 0, 1, 1, 2, 3, 5, 8, … folgen fib(n) = fib(n − 1) + fib(n − 2). Direkt als Rekursion geschrieben, macht fib(10) = 55 genau 177 Aufrufe, fib(20) macht 21 891 und fib(30) macht 2 692 537, weil dieselben kleineren Werte immer wieder berechnet werden. Sich schon gefundene Antworten zu merken oder mit einer Schleife von unten aufzubauen, beseitigt diese Verschwendung.