Rekursion
IN-SA TB #017–022
Definition
Unter Rekursion versteht man den Aufruf einer Methode (Operation / Funktion) durch sich selbst. Bei jedem (rekursiven) Aufruf der Methode wird dabei eine neue Instanz dieser Methode gestartet.
def blabla(x):
return blabla(x - 1) # ruft sich selbst auf
Voraussetzungen für korrekte Rekursion
Eine Rekursion muss zwei Bedingungen erfüllen:
- Rekursionsanfang (direkter Fall / Basisfall): Es darf keine „unendliche Schleife" entstehen. Es muss einen Basisfall geben, der die Kette der rekursiven Aufrufe beendet.
- Rekursionsschritt (Selbstaufruf / Rekursionsbedingung): Es existiert ein Selbstaufruf.
Grundprinzip: Divide and Conquer (Teile und Herrsche)
Die Rekursion folgt dem informatischen Grundprinzip:
Devide and Conquer – teile und herrsche
Bei diesem Prinzip wird ein Problem in mehrere kleinere Teile zerlegt. Diese Teilprobleme werden gelöst und anschließend werden die Teillösungen wieder zusammengebaut.
Beispiel: Fakultät
Mathematische Definition
n! = { 1, falls n = 1 (Rekursionsanfang); n · (n − 1)!, falls n > 1 (Rekursionsschritt) }
Mit Zahlen
5! = 5 × 4! = 5 × 24 = 120
4! = 4 × 3! = 4 × 6 = 24
3! = 3 × 2! = 3 × 2 = 6
2! = 2 × 1! = 2 × 1 = 2
1! = 1
In Python
def fak(n):
if n == 1:
return 1
else:
return n * fak(n - 1)
Operationskette (rekursiver Abstieg und Aufstieg)
fak(4) → 4 × fak(3) → 24
fak(3) → 3 × fak(2) → 6
fak(2) → 2 × fak(1) → 2
fak(1) → 1
Der Abstieg ist die Phase der Selbstaufrufe, der Aufstieg ist die Phase der Rückgaben.
Endrekursion
Eine Rekursion heißt endrekursiv, wenn der rekursive Aufruf die letzte Aktion vor der Rückgabe ist.
D.h. die Berechnung erfolgt bereits während des Abstiegs (wird nebenbei durchgereicht), sodass die Rückgabewerte beim Aufstieg nicht mehr weiter verrechnet werden müssen. Das Ergebnis liegt schon am Ende des Abstiegs vor.
Endrekursive Fakultät
def fakend(n, e):
if n == 1:
return e
else:
return fakend(n - 1, n * e) # Berechnung passiert im Parameter!
Aufrufkette (endrekursiv)
fakend(4, 1)
fakend(3, 4)
fakend(2, 12)
fakend(1, 24) → 24
Das Ergebnis 24 liegt bereits am Ende des Abstiegs vor – kein Aufstieg nötig!
Vergleich: Nicht endrekursiv vs. endrekursiv
Nicht endrekursiv (fak) | Endrekursiv (fakend) | |
|---|---|---|
| Berechnung | Beim Aufstieg | Beim Abstieg |
| Ergebnis liegt vor | Erst ganz oben am Ende | Schon am tiefsten Punkt |
| Aufruf ist letzte Aktion | ❌ (n * fak(n-1) – Multiplikation kommt nach dem Aufruf) | ✅ |
Lineare vs. Baumartige (Kaskadenartige) Rekursion
Lineare Rekursion
Eine Rekursion heißt linear, wenn im Rumpf der rekursiv definierenden Methode (höchstens) ein rekursiver Selbstaufruf vorkommt.
Beispiel: Fakultät
def fak(n):
if n == 1:
return 1
else:
return n * fak(n - 1) # genau 1 Selbstaufruf
Nicht-lineare / Baumartige (Kaskadenartige) Rekursion
Eine Rekursion heißt baumartig, wenn im Rumpf der rekursiv definierenden Methode mehr als ein rekursiver Selbstaufruf vorkommt (2, 3, ...).
Beispiel: Fibonacci-Folge
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n - 1) + fib(n - 2) # 2 Selbstaufrufe!
Aufrufbaum von fib(5)
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \
fib(2) fib(1) fib(1) fib(0)
/ \
fib(1) fib(0)
Die Aufrufe verzweigen sich wie ein Baum → viele Mehrfachberechnungen! (ineffizient)
Zusammenfassung
| Begriff | Bedeutung |
|---|---|
| Rekursionsanfang | Basisfall, der die Rekursion stoppt |
| Rekursionsschritt | Selbstaufruf mit vereinfachtem Argument |
| Abstieg | Phase der rekursiven Selbstaufrufe |
| Aufstieg | Phase der Rückgaben |
| Endrekursion | Berechnung im Abstieg, kein Aufstieg nötig |
| Lineare Rekursion | Genau 1 Selbstaufruf im Methodenrumpf |
| Baumartige Rekursion | Mehr als 1 Selbstaufruf im Methodenrumpf |