Rekursion ist eine Form der Wiederholung, bei der sich eine Funktion in ihrem eigenen Rumpf selbst aufruft.
Dabei wird ein großes Problem in kleinere, gleichartige Teilprobleme zerlegt, bis ein Trivialfall erreicht ist. Dort verhindert einen Abbruchbedingungen, dass der Selbstaufruf unendlich weiterläuft.
Rekursion arbeitet nach dem Divide and Conquer-Prinzip (Teile und Herrsche)
Iteration und Rekursion können grundsätzlich ineinander umgewandelt werden. Es sollte je Problemstellung entschieden werden, welche Form sich anbietet.
| Kriterium | Rekursion | Iteration |
|---|---|---|
| Funktionsweise | Funktion ruft sich selbst auf | Schleifen wie for oder while |
| Abbruch | Benötigt klare Abbruchbedingung | Schleifenbedingung steuert Ende |
| Speicherbedarf | Höher (Call-Stack) | Geringer |
| Lesbarkeit | Oft eleganter bei Teile und Herrscheproblemen | Häufig klarer bei einfachen Abläufen |
| Performance | Kann langsamer sein | Meist schneller |
Beispiel: https://www.rfdz-informatik.at/wp-content/uploads/2020/10/RE_I_Rekursion-Iteration.pdf
Typisch rekursive Probleme sind
def fak(n):
"""
Diese Funktion berechnet die Fakultät von n (n!).
"""
# Trivialfall
if n == 0:
return 1
# Rekursive Vereinfachung des Problems
return n * fak(n-1)
def fib(n):
"""
Diese Funktion berechnet die n-te Stelle der Fibonnaci-Folge.
"""
# Trivialfall
if n == 1 or n == 2:
return 1
# Rekursive Vereinfachung des Problems
return fib(n-1) + fib(n-2)
print(fak(5))
print(fib(5))