Einführung
Rekursion ist ein mächtiges Konzept in der Programmierung, bei dem eine Funktion sich selbst aufruft.
Am Anfang ist das vielleicht etwas knifflig zu verstehen, aber sobald du die Grundlagen beherrschst, wird sie zu einem wertvollen Werkzeug beim Lösen komplexer Probleme.
In diesem Tutorial schauen wir uns die Rekursion in JavaScript anhand leicht verständlicher Beispiele an.
Was ist Rekursion?
Von Rekursion sprichst du, wenn eine Funktion sich selbst aufruft, sei es direkt oder indirekt.
Das ähnelt einer Schleife, aber dabei zerlegst du ein Problem in kleinere, handlichere Teilprobleme.
Beispiel 1: Countdown
Fangen wir mit einem einfachen Beispiel an: einer Countdown-Funktion.
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
In diesem Beispiel:
-
Basisfall: Wenn
num kleiner oder gleich 0 wird, gibt die Funktion „Blastoff!“ aus und ruft sich nicht mehr selbst auf.
-
Rekursiver Fall: Die Funktion gibt das aktuelle
num aus und ruft sich selbst mit num - 1 auf.
Beispiel 2: Fakultät
Schauen wir uns nun ein klassisches Beispiel für Rekursion an: die Berechnung der Fakultät einer Zahl.
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
In diesem Beispiel:
-
Basisfall: Wenn
n 0 oder 1 ist, gibt die Funktion 1 zurück.
-
Rekursiver Fall: Die Funktion multipliziert
n mit der Fakultät von n - 1.
Wichtige Konzepte
Basisfall
Jede rekursive Funktion muss mindestens einen Basisfall haben, also eine Bedingung, bei der die Funktion aufhört, sich selbst aufzurufen.
Ohne einen Basisfall würde die Rekursion endlos weiterlaufen und zu einem Stack Overflow führen.
Rekursiver Fall
Der rekursive Fall legt fest, wie die Funktion sich selbst mit einer kleineren oder einfacheren Version des Problems aufruft.
Vor- und Nachteile der Rekursion
Vorteile:
- Elegante Lösung für bestimmte Probleme.
- Bildet das Konzept der mathematischen Induktion nach.
Nachteile:
- Kann weniger effizient sein als iterative Lösungen.
- Kann bei tiefer Rekursion zu einem Stack Overflow führen.
Fazit
Rekursion ist eine wertvolle Technik, mit der du komplexe Probleme vereinfachen kannst, indem du sie in kleinere, handlichere Teilprobleme zerlegst.
Basisfälle und rekursive Fälle zu verstehen ist entscheidend, um in JavaScript effektive rekursive Lösungen zu schreiben.
Mehr erfahren:
Anleitung
Du betreibst eine Pizzeria und bietest drei Sorten Pizza an:
- Margherita: 7 $
- Caprese: 9 $
- Formaggio: 10 $
Wenn Kundinnen und Kunden möchten, können sie eine unbegrenzte Anzahl zusätzlicher Optionen hinzufügen: entweder "ExtraSauce" für 1 $ oder "ExtraToppings" für 2 $.
Deine Aufgabe ist es, Code zu schreiben, der den Kunden dabei hilft, die Kosten zu ermitteln.
Berechne den Preis einer Pizza
Der Name der Pizza wird als erstes Argument übergeben, danach folgt eine unbegrenzte Anzahl zusätzlicher Optionen. Berechne den Preis der Pizza in Dollar.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
Berechne den Gesamtpreis einer Bestellung
Deine Funktion wird mit einer Liste von PizzaOrders aufgerufen und soll den Gesamtpreis der Bestellung in Dollar zurückgeben.
Jede PizzaOrder hat eine pizza-Eigenschaft (den Namen der Pizza) und eine extras-Eigenschaft (die Liste der zusätzlichen Optionen).
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
Du wirst feststellen, dass du das nicht mit Rekursion schreiben kannst, denn ein Test mit einer enormen Anzahl an Bestellungen führt zu einem Fehler mit der Meldung Maximum call stack size exceeded.
Keine Sorge, das ist Absicht. Versuche, diese Funktion mit einer imperativen Schleife umzusetzen!
Du hast viele Möglichkeiten, zum Beispiel reduce oder eine for-Schleife zu verwenden, aber nicht nur diese.
Wenn der JavaScript-Interpreter den JavaScript-Code ausführt, behält er auf einer Datenstruktur namens „Stack“ den Überblick darüber, welche Funktionen er betreten (aufzurufen begonnen) hat.
Wenn die Funktion zurückkehrt (endet), wird sie vom Stack entfernt.
Dieser Stack hat jedoch eine begrenzte Größe.
Der häufigste Fehler ist eine rekursive Funktion, die nie endet.
Jeder Aufruf wird auf den Stack gelegt, aber bevor er zurückkehrt, wird ein weiterer Aufruf auf den Stack gelegt.
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
Der Stacktrace dieses Fehlers zeigt immer wieder dieselbe Zeile, was sinnvoll ist, weil die Funktion sich selbst aufruft.
Auch wenn das in den meisten Fällen keinen echten praktischen Nutzen hat, kannst du herausfinden, wie hoch dieser Stack werden kann.
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
Für einen Fehler im Aufrufstack, der durch eine synchrone rekursive Funktion verursacht wird, gibt es nur zwei praktikable Lösungen:
- Stelle sicher, dass die Funktionen zurückkehren, bevor das Stack-Limit erreicht wird, meist indem du einen Basisfall hinzufügst oder korrigierst.
- Schreibe die rekursive Funktion in eine imperative Schleife um. Diese führt den Schleifenblock aus, ohne eine Funktion betreten zu müssen, und vergrößert so den Stack nicht.
Lernübung
