Die Fakultät rekursiv berechnen in Python
In dieser Lektion schreibst du eine rekursive Funktion für die Fakultät und lernst, welche Rolle die Abbruchbedingung spielt.
Einführung
Das Problem
Manche Probleme lassen sich natürlich durch eine kleinere Version von sich selbst beschreiben: Ein Ordner enthält Ordner, ein Stammbaum enthält kleinere Stammbäume, n! ist n mal (n - 1)!. Mit Rekursion schreibst du Code, der solchen Definitionen direkt folgt.
Stell es dir so vor
Rekursion ist wie eine Reihe von Leuten, die eine Frage weitergeben. Um 6! auszurechnen, fragt die erste Person die nächste nach 5! und wartet. Diese fragt nach 4!, und so weiter, bis jemand nach 1! gefragt wird und sofort antworten kann. Dann wandern die Antworten die Reihe zurück, und jede Person multipliziert ihre eigene Zahl dazu.
factorial(6)🙋 Die erste Person: 6 × die Antwort, auf die sie wartetnumber * factorial(number - 1)➡️ Die nächste Person dasselbe fragen, nur mit einer kleineren Zahlif number <= 1: return 1🛑 Die letzte Person antwortet sofort: 1720⬅️ Die Antworten wandern zurück: 720Eine rekursive Funktion ruft sich selbst mit einer kleineren Eingabe auf, bis sie einen Basisfall erreicht, den sie direkt beantworten kann. Hier gilt factorial(n) = n × factorial(n - 1) und factorial(1) = 1.
Das Wichtigste
if number <= 1: return 1ist der Basisfall; ohne ihn würden die Aufrufe nie enden.return number * factorial(number - 1)ruft dieselbe Funktion mit einer kleineren Zahl auf.factorial(6)wartet auffactorial(5), das auffactorial(4)wartet, bis hinunter zufactorial(1).raise ValueError(...)weist negative Zahlen ab, die den Basisfall sonst nie erreichen würden.
Wann verwendet man das?
- Probleme, die über kleinere Versionen definiert sind: Bäume, Ordner, verschachtelte Daten.
- Divide-and-Conquer-Algorithmen wie Merge Sort.
- Lernen, wie der Call Stack funktioniert.
Wann du es nicht brauchst
- Einfache Wiederholung wie die Fakultät in echtem Code: Eine Schleife oder
math.factorialist schneller und hat keine Tiefengrenze. - Sehr tiefe Eingaben: Python stoppt bei etwa 1.000 verschachtelten Aufrufen mit RecursionError.
So funktioniert es
Klicke auf Schritt, um jedem Aufruf zu folgen. Neue Aufrufe landen auf dem Aufrufstapel, und jeder gibt seinen Wert an den Aufrufer zurück.
Beispielcode
def factorial(number):
if number < 0:
raise ValueError("Factorial is undefined for negative numbers")
if number <= 1:
return 1
return number * factorial(number - 1)
print(factorial(6))
Ergebnis der Ausführung
720
Erklärung des Codes
Ist number gleich 0 oder 1, gibt die Funktion sofort 1 zurück. Das ist die Abbruchbedingung, die verhindert, dass die Rekursion endlos läuft. Für alle anderen Werte gibt die Funktion number mal factorial(number - 1) zurück. Jeder rekursive Aufruf wird auf dem Aufrufstapel (call stack) abgelegt, die Rekursionstiefe ist also O(n).
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungen zur Vertiefung
Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
Den Basisfall vergessen
Die Funktion ruft sich endlos selbst auf, bis Python einen RecursionError auslöst.
def factorial(number):
return number * factorial(number - 1)
def factorial(number):
if number <= 1:
return 1
return number * factorial(number - 1)
Lektion fertig?
Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
- Fakultät Multipliziere alle positiven ganzen Zahlen bis n. Einfach
- Recursive Power Compute a power recursively by halving the exponent. Mittel