Algorithmuspro

Rekursion: Fakultät

Eine Funktion, die sich selbst mit einer kleineren Eingabe aufruft, bis sie einen Fall direkt beantworten kann.

Zeit: O(n)
Speicher: O(n)

// Schritt für Schritt

Schritt 1 / 11

1function factorial(n) {2  if (n <= 1) return 1;3  return n * factorial(n - 1);4}

depth: = 1

Rufe factorial(4) auf.

Tipp: Mit den Pfeiltasten durch die Schritte gehen.

// pro-lektion

Den ganzen Durchlauf freischalten

Diese Lektion ist Teil von Pro. Pro schaltet jeden Schritt jeder Lektion frei, dazu Muster-Übungen und Fortschrittsauswertungen.

Preise ansehen

So funktioniert es

factorial(4) kann nicht sofort antworten, also fragt es factorial(3), das wiederum factorial(2) fragt, und so weiter. Jeder wartende Aufruf liegt auf dem Aufrufstapel. Wenn factorial(1) den Basisfall erreicht und 1 zurückgibt, fließen die Antworten nach oben zurück, und jeder wartende Aufruf beendet seine Multiplikation. Jede rekursive Funktion braucht einen Basisfall und einen Schritt, der die Eingabe verkleinert. O(n) Zeit und O(n) Speicher für den Aufrufstapel.

Dieses Muster erkennen üben →