634 Anhang
Rekursive Funktionen
8. Rekursion
Wenn Sie einer Funktion einen Namen geben, können Sie damit etwas recht Interessantes anstellen:
Sie können dafür sorgen, dass die Funktion sich selbst aufruft. Das bezeichnet man als Rekursion oder
rekursiven Funktionsaufruf.
Aber warum sollte man das tun? Weil manche Probleme eben rekursiver Natur sind. Hier ein Beispiel
aus der Mathematik: ein Algorithmus zur Berechnung der Fibonaccifolge. Sie sieht wie folgt aus:
0, 1, 1, 2 , 3, 5, 8, 13, 21, 34, 55, 89, 144 … und so weiter.
Um eine Fibonaccizahl zu berechnen, haben wir folgende Annahmen:
Fibonacciwert von 0 ist 1
Fibonacciwert von 1 ist 1
Die weiteren Zahlen der Folge werden berechnet, indem wir einfach die beiden vorigen Zahlen der
Folge addieren, wie hier:
Fibonacciwert von 2 ist Fibonacciwert von 1 + Fibonacciwert von 0 = 2
Fibonacciwert von 3 ist Fibonacciwert von 2 + Fibonacciwert von 1 = 3
Fibonacciwert von 4 ist Fibonacciwert von 3 + Fibonacciwert von 2 = 5
und so weiter. Der Algorithmus zur Berechnung von Fibonacciwerten ist in sich rekursiv, weil Sie zum
Berechnen der nächsten Zahl die Ergebnisse der beiden vorangehenden Fibonaccizahlen brauchen.
Um eine rekursive Funktion zur Berechnung von Fibonaccizahlen zu erstellen, können wir so vorgehen:
Um den Fibonacciwert von n zu berechnen, rufen wir die Fibonaccifunktion mit dem Argument n-1
auf, dann rufen wir die Funktion mit dem Argument n-2 auf und addieren die Ergebnisse.
Das wollen wir jetzt im Code abbilden. Wir beginnen mit den Basisannahmen für 0 und 1:
function bonacci(n) {
if (n === 0) return 1;
if (n === 1) return 1;
}
Wir starten mit einer Funktion, der wir n
als gesuchte Zahl in der Folge übergeben.
Ist die Zahl 0 oder
1
, geben wir
1
zurück.
Dies wird als Basisannahme der Funktion
bezeichnet, weil es hierbei keine rekursiven
Aufrufe gibt.
Das hier sind die Basisannahmen (Base Cases), also Fälle, die keine vorangehende
Fibonaccizahl benötigen, um berechnet zu werden. Es gilt als gute Praxis, sie zuerst zu
formulieren. Das können Sie sich so vorstellen: »Um eine Fibonaccizahl n zu berechnen,
gebe ich den Fibonacciwert von n-1 addiert mit dem Fibonacciwert von n-2 zurück.«
Dann wollen wir mal …
Sie sind hier � 635
Was übrig bleibt
function bonacci(n) {
if (n === 0) return 1;
if (n === 1) return 1;
return (bonacci(n-1) + bonacci(n-2));
}
Ist n weder 0 noch
1
, können wir den
Fibonacciwert einfach durch die Addition
von n-
1
und n-2 berechnen.
Wenn Sie die Rekursion noch nicht kennen, wirkt das ein bisschen wie Zauberei.
Tatsächlich werden hiermit aber Fibonaccizahlen berechnet. Wir wollen den Code
etwas aufräumen und dann testen:
function bonacci(n) {
if (n === 0 || n === 1) {
return 1;
} else {
return (bonacci(n-1) + bonacci(n-2));
}
}
for (var i = 0; i < 10; i++) {
console.log("Nächster Fibonacciwert für " + i + " ist " + bonacci(i));
}
Der gleiche Code, nur
etwas besser geschrieben.
JavaScript-Konsole
Der Fibonacciwert von 0 ist 1
Der Fibonacciwert von 1 ist 1
Der Fibonacciwert von 2 ist 2
Der Fibonacciwert von 3 ist 3
Der Fibonacciwert von 4 ist 5
Der Fibonacciwert von 5 ist 8
Der Fibonacciwert von 6 ist 13
Der Fibonacciwert von 7 ist 21
Der Fibonacciwert von 8 ist 34
Der Fibonacciwert von 9 ist 55
Und etwas Code
zum Testen.
Sorgen Sie für eine Basisannahme.
Wenn der rekursive Code keine Basisannahme
(»Base Case«) besitzt, die die Ausführung been-
det, läuft der Code quasi ewig weiter – wie eine Endlos-
schleife. Die Funktion ruft sich immer wieder selbst auf
und verbraucht irgendwann so viele Ressourcen, dass
Ihr Browser die Segel streicht. Wenn Sie rekursiven
Code schreiben und Ihr Browser plötzlich nicht mehr
reagiert, sollten Sie überprüfen, ob die Basisannahme
jemals erreicht wird.
Get JavaScript-Programmierung von Kopf bis Fuß now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
