Eine Matrjoschka-Puppe in einer Puppe
Rekursion heißt: Eine Funktion ruft sich selbst auf, mit einem kleineren Problem. Sie löst schwere Aufgaben, indem sie sie auf eine einfachere Fassung derselben Aufgabe zurückführt.
Eine russische Matrjoschka enthält eine kleinere Puppe, die wieder eine kleinere enthält, bis die kleinste da ist. So arbeitet eine rekursive Funktion.
Am Ende dieser Lektion
Notiz
Ich kann eine Funktion schreiben, die sich selbst aufruft.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Rekursion | eine Funktion ruft sich selbst auf | |
| Basisfall | der einfachste Fall, den die Funktion ohne Selbstaufruf beantwortet | |
| Rekursiver Fall | der Fall, in dem sich die Funktion mit einem kleineren Problem aufruft | |
| Aufrufstapel | der Stapel der Aufrufe, die noch auf ein Ergebnis warten | |
| Fakultät | das Produkt aller ganzen Zahlen von 1 bis n | 4! = 24 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Jede Rekursion hat zwei Teile
Eine rekursive Funktion hat immer zwei Teile. Der Basisfall ist so einfach, dass die Funktion ihn gleich beantwortet. Der rekursive Fall ruft die Funktion mit einem kleineren Wert wieder auf.
Ohne Basisfall hört sie nie auf. Ohne kleineren Wert kommt sie dem Basisfall nie näher.
Runterzählen: ein erstes Beispiel
def runterzaehlen(n):
if n == 0: # Basisfall: hier hört es auf.
print("los")
else:
print(n)
runterzaehlen(n - 1) # Rekursiver Fall: ein kleinerer Wert.
runterzaehlen(3) # Ändere die 3 auf 5.
Beispiel: die Fakultät rekursiv
Die Fakultät von 4 ist 4 mal 3 mal 2 mal 1, also 24. Das lässt sich rekursiv sagen: Die Fakultät von n ist n mal die Fakultät von n minus 1. Die Fakultät von 1 ist 1.
Der letzte Satz ist der Basisfall, der davor der rekursive Fall.
Bevor du anfängst
Notiz
Drück oben in der Leiste auf Lab starten und warte, bis JupyterLab läuft. Die Schaltflächen Ausführen tippen ihren Befehl in das Terminal neben dem Lab. Jeder startet Python im Container jupyter.
Runterzählen und Fakultät in rekursion.py schreiben
docker exec jupyter sh -c "printf 'def runterzaehlen(n):\n if n == 0:\n print(\"los\")\n else:\n print(n)\n runterzaehlen(n - 1)\n\nrunterzaehlen(3)\n\ndef fakultaet(n):\n if n == 1:\n return 1\n return n * fakultaet(n - 1)\n\nprint(fakultaet(5))\n' > rekursion.py"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die rekursiven Funktionen starten
docker exec jupyter python3 rekursion.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Der Aufrufstapel merkt sich, was noch wartet
Bei fakultaet(3) ruft sich die Funktion auf, bevor sie rechnen kann. Jeder wartende Aufruf liegt auf dem Aufrufstapel, so wie Teller auf einem Stapel. Erst der oberste kann fertig werden.
Ist der Basisfall erreicht, werden die Aufrufe von oben nach unten abgearbeitet.
Beispiel: die Aufrufe von fakultaet(3)
| Aufruf | Wartet auf | Ergebnis |
|---|---|---|
| fakultaet(3) | fakultaet(2) | 3 mal 2 = 6 |
| fakultaet(2) | fakultaet(1) | 2 mal 1 = 2 |
| fakultaet(1) | nichts, Basisfall | 1 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ohne Basisfall läuft der Stapel über
Fehlt der Basisfall, ruft sich die Funktion immer weiter auf. Der Aufrufstapel wächst, bis Python bei 1000 Aufrufen abbricht. Der Fehler heißt RecursionError.
Der nächste Befehl zeigt das mit einer Funktion, die nie aufhört. Er fängt den Fehler ab und gibt nur zu tief aus.
Das Limit des Aufrufstapels zeigen
docker exec jupyter python3 -c "print(__import__('sys').getrecursionlimit())"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Eine endlose Rekursion in tief.py schreiben
docker exec jupyter sh -c "printf 'def endlos(n):\n return endlos(n + 1)\n\ntry:\n endlos(1)\nexcept RecursionError:\n print(\"zu tief\")\n' > tief.py"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die endlose Rekursion starten
docker exec jupyter python3 tief.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele denken, ein Selbstaufruf sei ein Fehler, weil sich die Funktion ja selbst braucht. Er ist erlaubt und nützlich, solange es einen Basisfall gibt und jeder Aufruf dem Basisfall näher kommt. Rufst du fakultaet(n) statt fakultaet(n - 1) auf, kommst du nie an.
Weiterführend: Merge Sort rekursiv
In der Lektion über das Sortieren hast du Paare verschmolzen. Man kann es auch rekursiv sagen: Teile die Liste in zwei Hälften, sortiere jede Hälfte mit derselben Funktion und verschmilz beide. Was ist hier der Basisfall? Und wie viele Elemente hat die Liste dann?