JavaScript/Funktion/Rekursive Funktionen

Eine Rekursion (lat. recurrere, zurücklaufen) bezeichnet als Programmiertechnik einen Funktion, die sich zur Lösung ihrer Aufgabe selbst aufruft. So etwas ergibt natürlich nur dann einen Sinn, wenn

• der rekursive Aufruf – der Rekursionsschritt – mit anderen Parametern erfolgt
• es eine Parameterkonstellation gibt, bei der die Funktion sich nicht selbst aufruft, dies ist der Rekursionskern
• sichergestellt ist, dass der Rekursionskern erreicht wird

Die Idee dabei ist, dass man ein „schwieriges“ Problem so löst, dass man es auf ein „einfacheres“ Problem zurückführt und dann die Lösung des einfacheren Problems verwendet, um das schwierigere Problem endgültig zu lösen. Dieses einfachere Problem kann gleicher Art sein – dann ruft die Funktion sich direkt selbst auf. Es kommt aber auch vor, dass Funktion A zunächst eine Funktion B aufruft und diese wiederum A verwendet, das nennt man eine indirekte Rekursion.

Beispiel: Fakultät

Ein klassisches Beispiel für Rekursion ist der Fakultätsoperator. Er wird als Ausrufezeichen geschrieben, und bedeutet: Ermittle das Produkt der Zahlen von 1 bis zu der Zahl, auf die der Operator angewendet wird. Unter 5! versteht der Mathematiker also das Produkt 1·2·3·4·5=120. Die Fakultät wird von Mathematikern rekursiv definiert:

   n! = 1, wenn n=0 oder n=1
   n! = n * (n-1)!, wenn n > 1

Fakultät als Rekursion

Diese Definition lässt sich in JavaScript ganz einfach nachprogrammieren:

Fakultät, rekursiv

function fakultät(n) {
   return (n > 1) ? n * fakultät(n-1) : 1;
}
console.log("5! = ", fakultät(5));

Durch die Verwendung des Bedingungsoperators ?: lässt sich die Funktion als Einzeiler formulieren.

Wird fakultät(5) aufgerufen, gelangt die Funktion in den n > 1-Teil der Rekursion und führt einen Schritt aus: Sie ruft fakultät(4) auf und multipliziert das Ergebnis mit 5. Der Aufruf von fakultät(4) führt auf fakultät(3), dies auf fakultät(2) und fakultät(1). Hier gelangt die Rekursion an ihren Kern, sie gibt lediglich 1 zurück.

JavaScript hat sich für jeden Aufruf von fakultät einen eigenen Aufrufkontext gemerkt. Nach der Rückkehr aus fakultät(1) in den Aufruf von fakultät(2) wird dessen Kontext wiederhergestellt, d. h. n ist jetzt wieder 2 und kann mit dem Ergebnis von fakultät(1) multipliziert werden. Das Ergebnis wird zurückgegeben und JavaScript kehrt in den Kontext von fakultät(3) zurück, so dass es nun das Ergebnis von fakultät(2)<code> mit 3 multiplizieren kann. Das geht so lange weiter, bis der Stapel von Aufrufkontexten wieder abgebaut ist und JavaScript zum eigentlichen Aufrufer zurückkehren kann, der das Ergebnis von <code>fakultät(5) auf die Konsole ausgibt.

Der Vorteil einer rekursiven Funktion ist, dass sich etliche Probleme recht gut dadurch rekursiv definieren lassen und als Schleife nur sehr umständlich realisierbar sind. Durch den neuen Aufrufkontext ist die Lösung des „einfacheren“ Problems von der Lösung des „schwierigeren“ Problems getrennt und verwendet ihre eigenen Variablen. Programmiert man eine Schleife, muss man diese Berechnungskontexte eventuell getrennt voneinander speichern. Das ist nicht immer einfach.

Fakultät als Schleife

Im Falle der Fakultät ist eine Lösung als Schleife aber genauso einfach, deshalb ist dieses klassische Beispiel auch eins der schlechtesten:

Fakultät, iterativ

function fakultät(n) {
   let ergebnis = 1;
   for (let i=2; i<=n; i++) {
      ergebnis = ergebnis * i;
   }
   return ergebnis;
}

Es genügt, die Schleife bei 2 zu starten, weil eine Multiplikation mit 1 nichts bewirkt.

Beispiel: str_repeat

Die n-fache Wiederholung einer Zeichenkette lässt sich ebenfalls als Rekursion formulieren. Die Notwendigkeit eines solchen Eigenbaus ist seit 2017 allerdings nicht mehr gegeben (siehe String.prototype.repeat), wir wollen ihn als Beispiel aber trotzdem zeigen.

Stringwiederholung, rekursiv

function str_repeat(str, num) {
   return (num > 0) ? str + str_repeat(str, num - 1) : "";
}
console.log(str_repeat("abc", 5)); //abcabcabcabcabc

Auch hier ist die Funktion als Einzeiler erstellbar. str_repeat ruft sich selbst auf, bis n nicht mehr größer als 0 ist, und gibt als Rekursionskern den leeren String zurück. Der Aufruf von str_repeat("foo", 0) führt dadurch zum leeren String.

Der Ablauf lässt sich so darstellen:

1. console.log(str_repeat("abc", 5));
2. console.log("abc" + str_repeat("abc", 4));
3. console.log("abc" + "abc" + str_repeat("abc", 3));
4. console.log("abc" + "abc" + "abc" + str_repeat("abc", 2));
5. console.log("abc" + "abc" + "abc" + "abc" + str_repeat("abc", 1));
6. console.log("abc" + "abc" + "abc" + "abc" + "abc" + str_repeat("abc", 0));
7. console.log("abc" + "abc" + "abc" + "abc" + "abc" + "");
8. console.log("abcabcabcabcabc");

Beispiel: Türme von Hanoi

Ein besseres Beispiel für einen rekursiven Algorithmus sind die Türme von Hanoi. Hier ruft sich die bewege-Funktion sogar zweimal pro Schritt auf. Der Algorithmus ist in der Wikipedia gut beschrieben, lesen Sie gerne dort nach, um das Beispiel kennenzulernen.

Probleme

Rekursive Programmierung hat den Nachteil, dass ein rekursives Programm pro Schritt einiges an Aufwand benötigt. Schließlich muss jedesmal ein neuer Aufrufkontext hergestellt werden. Dieser Aufwand findet in der JavaScript-Laufzeitumgebung statt, ist aber deutlich zu merken. Die iterative Version der Fakultät ist deutlich schneller als die rekursive Version.

Diese Aufrufkontexte benötigen Speicher. JavaScript legt sie in einer Datenstruktur an, die man Stack (Stapel) nennt. Dieser Stack ist aber nicht unbegrenzt groß, und bei sehr tiefen Rekursionen kann es vorkommen, dass das Programm mit einem Überlauf dieses Stapels abbricht. Immerhin merkt JavaScript das rechtzeitig. In älteren C-Programm kann es vorkommen, dass ein Stapelüberlauf unbemerkt bleibt und sich Stapel und andere Daten gegenseitig überschreiben. Da zum Aufrufkontext auch die Stelle gehört, an die das Programm nach Ende der Funktion zurückkehren muss, kann dieses Überschreiben dazu führen, dass der Computer an eine komplett falsche Stelle im Speicher springt, wo vielleicht gar kein Programm steht, und dann abstürzt. Dieses "rechtzeitige Bemerken" des Stapelüberlaufs ist aber ein weiterer Arbeitsschritt, den JavaScript ausführen muss und der die Rekursion ausbremst.

Endrekursion

Es gibt Programmiersprachen, die überhaupt keine Schleifen kennen. Statt dessen verlangen sie vom Programmierer, Schleifen durch Rekursionen zu lösen. Das klingt verrückt, hat aber den Vorteil, dass man die Daten von einem Schleifendurchlauf explizit an den nächsten Schleifendurchlauf übergeben muss. In einer Schleife hingegen hat man Variablen, die sich pro Durchlauf verändern, und manchmal macht man das eben auch falsch oder vergisst eine dieser Variablen.

Um zu verhindern, dass bei länger laufenden Schleifen der Stapelspeicher überläuft, verwendet man in diesen Fällen eine Endrekursion (engl. tail recursion). Das bedeutet, dass die Funktion sich selbst aufruft und das Ergebnis dieses Aufrufs sofort und unverändert zurückgibt. Dazu muss man die Fakultätsfunktion etwas umschreiben:

Fakultät, endrekursiv

function fakultät(n, product=1) {
   if (n > 1)
      return fakultät(n-1, n*product);
   else
      return product;
}

Der Aufruf fakultät(5) (mit nur einem Parameter) verwendet den Defaultwert 1 für den zweiten Parameter, product. Der erste rekursive Aufruf berechnet daher 5*1 als Zwischenergebnis für das Produkt und setzt mit dem Aufruf fakultät(4, 5) fort. Darin ist n noch größer als 1, so dass der nächste Aufruf fakultät(3, 20) lautet. Weiter geht es mit fakultät(2, 60) und fakultät(1, 120). Nun ist n=1 und es wird lediglich das Produkt zurückgegeben.

Eine Programmierumgebung, die Endrekursionen erkennt, weiß nun, dass es für den rekursiven Aufruf nicht nötig ist, den Kontext der aufrufenden Funktion zu speichern, und kann deshalb den Aufrufkontext eines Schritts einfach durch den Kontext des folgenden Schritts ersetzen, wodurch beliebig tiefe Rekursionen möglich werden.

Zur Zeit (Juli 2024) werden Endrekursionen nur von Safari unterstützt.