Rekursion

Der Akt der Selbstaufrufung einer Funktion, Rekursion, wird verwendet, um Probleme zu lösen, die kleinere Teilprobleme enthalten. Eine rekursive Funktion kann zwei Eingaben erhalten: einen Basisfall (beendet die Rekursion) oder einen rekursiven Fall (setzt die Rekursion fort).

Beispiele

Rekursive Funktion ruft sich selbst auf, bis Bedingung erfüllt ist

Der folgende Python-Code definiert eine Funktion, die eine Zahl übernimmt, sie ausgibt und sich dann erneut mit dem Wert der Zahl -1 aufruft. Sie fährt fort, bis die Zahl gleich 0 ist, in diesem Fall stoppt sie.

def recurse(x):
 if x > 0:
 print(x)
 recurse(x - 1)
recurse(10)

Die Ausgabe wird wie folgt aussehen:

10
9
8
7
6
5
4
3
2
1

Rekursion ist durch die Stapelgröße begrenzt

Der folgende Code definiert eine Funktion, die die maximale Größe des Aufrufstapels zurückgibt, der in der JavaScript-Laufzeit verfügbar ist, in der der Code ausgeführt wird.

const getMaxCallStackSize = (i) => {
 try {
 return getMaxCallStackSize(++i);
 } catch {
 return i;
 }
};
console.log(getMaxCallStackSize(0));

Häufige Anwendungsbeispiele

Fakultät

const factorial = (n) => {
 if (n === 0) {
 return 1;
 }
 return n * factorial(n - 1);
};
console.log(factorial(10));
// 3628800

Fibonacci

const fibonacci = (n) => (n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2));
console.log(fibonacci(10));
// 55

Reduzieren

const reduce = (fn, acc, [cur, ...rest]) =>
 cur === undefined ? acc : reduce(fn, fn(acc, cur), rest);
console.log(reduce((a, b) => a + b, 0, [1, 2, 3, 4, 5, 6, 7, 8, 9]));
// 45

Siehe auch

• Rekursion (Informatik) auf Wikipedia
• Weitere Details zur Rekursion in JavaScript