Rekursion in JavaScript

Problem

Wie viele Anordnungen gibt es?

Im Regal stehen 5 Bücher. Auf wie viele Arten kannst du sie anordnen? Für den ersten Platz gibt es 5 Möglichkeiten, für den zweiten 4, dann 3, 2 und 1: 5 · 4 · 3 · 2 · 1 = 120. Das ist die Fakultät, geschrieben 5!.

Mit einer Schleife kannst du das schon:

function factorialLoop(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorialLoop(5));

Sieh es auch so: 5! = 5 · 4!. Und 4! = 4 · 3!. Die Aufgabe wird über dieselbe Aufgabe, nur kleiner gelöst. Kann die Funktion genau das sagen?

Die Idee

Eine Funktion, die sich selbst aufruft

Sie kann. Eine Funktion, die sich selbst aufruft, nennt man rekursiv, und das Vorgehen Rekursion.

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(5));

Zwei Dinge sorgen dafür, dass es funktioniert:

Ein Basisfall. Ein Fall, der direkt gelöst wird, ohne neuen Aufruf. Hier: 1! = 1.
Eine kleinere Aufgabe. Jeder Aufruf ruft sich selbst mit einer Zahl auf, die näher am Basisfall liegt: n - 1.

Sieh es dir an

Der Stapel der Aufrufe

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(3));  // 6

Schritt für Schritt, in Worten

Das Programm ruft factorial(3) auf.
Neuer Speicher für factorial mit n = 3.
3 ist nicht 1, also ruft die Funktion factorial(2) auf und wartet auf die Antwort.
Dasselbe noch einmal: factorial(2) ruft factorial(1) auf. Jeder Aufruf hat sein eigenes n.
n ist 1: Das ist der Basisfall. Er gibt 1 zurück, ohne sich noch einmal aufzurufen.
Die Antwort geht nach unten zurück: 2 * 1 = 2.
Und noch einmal: 3 * 2 = 6.
factorial(3) gibt 6 zurück, und das Programm gibt es aus.

Jeder Aufruf bekommt seinen eigenen Speicher mit seinem eigenen n. Sie stapeln sich übereinander und warten. Diesen Stapel nennt man Aufrufstapel (call stack). Wenn der Basisfall 1 zurückgibt, gehen die Antworten eine nach der anderen nach unten zurück, und der Stapel löst sich auf.

Probier es aus

Runter und wieder rauf

Was gibt das Programm aus?

function steps(n) {
  if (n === 0) {
    return;
  }
  console.log(`runter ${n}`);
  steps(n - 1);
  console.log(`rauf ${n}`);
}

steps(2);

Antwort

runter 2
runter 1
rauf 2
rauf 1

runter 2
runter 1
rauf 1
rauf 2

runter 2
rauf 2
runter 1
rauf 1

Probier es aus

Finde den Fehler

sumTo(4) soll 1 + 2 + 3 + 4 = 10 zurückgeben. Stattdessen bricht das Programm mit RangeError: Maximum call stack size exceeded ab. In welcher Zeile ist der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Rekursion oder Schleife?

Die Fakultät lässt sich mit einer Schleife oder mit Rekursion schreiben. Hier ist die Schleife die bessere Wahl: Sie häuft nicht für jeden Aufruf Speicher an, und für 100 000 Aufrufe reicht der Stapel nicht.

Rekursion ist dort natürlich, wo eine Sache kleinere Sachen derselben Art enthält: ein Ordner mit Ordnern darin, eine Kategorie mit Unterkategorien, ein Ast mit Ästen. Solchen Aufgaben begegnest du später im Kurs. Dort wird eine Schleife umständlich, während die rekursive Funktion kurz bleibt.

Genauer, für Neugierige

Die Fakultät schreibt man oft mit dem Basisfall 0! = 1 (if (n === 0)). Dann funktioniert sie auch für 0.

In JavaScript ist jede Zahl eine Dezimalzahl (double), und große ganze Zahlen werden nur ungefähr gespeichert. Bis 22! ist das Ergebnis genau, aber 23! ist schon gerundet. Für genaue ganze Zahlen ohne Grenze gibt es BigInt: eine Zahl mit einem n am Ende (23n):

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

function factorialBig(n) {
  if (n === 1n) {
    return 1n;
  }
  return n * factorialBig(n - 1n);
}

console.log(factorial(23));
console.log(factorialBig(23n));

2.585201673888498e+22
25852016738884976640000n

Probier es aus

Bring die Zeilen in die richtige Reihenfolge

Die Funktion soll eine Potenz berechnen: power(2, 10) ist 1024. Bring ihre Zeilen in die richtige Reihenfolge.

}
function power(base, exp) {
}
if (exp === 0) {
return base * power(base, exp - 1);
return 1;

Übung

Rekursive Aufgaben

1. Fakultät auf zwei Arten. Schreib factorialLoop(n) mit einer for-Schleife und factorial(n) mit Rekursion. Lies eine Zahl ein und gib das Ergebnis beider Funktionen aus.

Die Fakultät von 5 ist 120
Die Fakultät von 5 ist 120

2. Quersumme. sumDigits(n): die letzte Ziffer (n % 10) plus die Quersumme des Rests (Math.trunc(n / 10)). Der Basisfall ist eine einstellige Zahl.

3. Fibonacci. Jede Zahl ist die Summe der zwei davor: 0, 1, 1, 2, 3, 5, 8… fib(n) gibt die n-te Zahl zurück. Probier es mit 10 und dann mit 45. Warum ist es so langsam? Hinweis: Wie oft wird jede Zahl ausgerechnet?

4. Palindrom. isPalindrome(s): Der erste und der letzte Buchstabe sind gleich, und die Mitte ist ein Palindrom. Der Basisfall ist ein Wort mit 0 oder 1 Buchstaben.

sumDigits(2024)
fib(10)
isPalindrome("neben")
isPalindrome("ABCDE")

8
55
true
false

Test

Teste dich

1. Was ist Rekursion?Eine Funktion, die sich selbst aufruftEine Schleife in einer FunktionZwei Funktionen mit demselben Namen

2. Warum braucht eine rekursive Funktion einen Basisfall?Damit sie aufhört, sich selbst aufzurufenDamit sie ein Ergebnis zurückgeben kannDamit sie schneller läuft

3. factorial(3) ruft factorial(2) auf, und das ruft factorial(1) auf. Wie viele Variablen n sind im Speicher, kurz bevor factorial(1) zurückkehrt?KeineDreiEine

4. Was passiert, wenn der Basisfall nie erreicht wird?Der Stapel läuft über, und das Programm bricht mit einem RangeError abDie Funktion gibt 0 zurückDas Programm läuft ewig, ohne Fehler

Rekursion

Cookies