Python - Rekursion: Ein Anfänger-Leitfaden

Hallo daar, zukünftige Python-Zauberer! Heute werden wir eine aufregende Reise in die Welt der Rekursion antreten. Keine Sorge, wenn es ein bisschen abschreckend klingt – ich verspreche, wir machen es Spaß und leicht verständlich. Also, holen Sie sich Ihr Lieblingsgetränk, machen Sie sich komfortabel und lassen Sie uns einsteigen!

Was ist Rekursion?

Stellen Sie sich vor, Sie stehen zwischen zwei Spiegeln, die sich gegenüberstehen. Sie sehen eine unendliche Anzahl von Reflexionen, richtig? Das ist ein bisschen wie Rekursion in der Programmierung! In einfachen Worten ist Rekursion, wenn eine Funktion sich selbst aufruft, um ein Problem zu lösen.

Lassen Sie uns mit einem einfachen Beispiel beginnen:

def countdown(n):
if n <= 0:
print("Start!")
else:
print(n)
countdown(n - 1)

countdown(5)

Wenn Sie diesen Code ausführen, sehen Sie:

5
4
3
2
1
Start!

Nun, lassen Sie uns das aufbrechen:

1. Wir definieren eine Funktion namens countdown, die eine Zahl n nimmt.
2. Wenn n 0 oder weniger ist, geben wir "Start!" aus.
3. Andernfalls geben wir n aus und rufen dann countdown erneut mit n - 1 auf.

Das ist Rekursion in Aktion! Die Funktion ruft sich selbst mit einer kleineren Zahl auf, bis sie Null erreicht.

Komponenten der Rekursion

Jede rekursive Funktion hat zwei Hauptkomponenten:

1. Basisfall: Dies ist die Bedingung, die die Rekursion stoppt.
2. Rekursiver Fall: Dies ist der Ort, an dem die Funktion sich selbst aufruft.

In unserem Countdown-Beispiel:

• Der Basisfall ist if n <= 0
• Der rekursive Fall ist countdown(n - 1)

Lassen Sie uns ein weiteres klassisches Beispiel anschauen: die Berechnung des Faktorials.

def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)

print(factorial(5))  # Output: 120

Hier ist, was passiert:

1. Wenn n 0 oder 1 ist, geben wir 1 zurück (dies ist unser Basisfall).
2. Andernfalls multiplizieren wir n mit dem Faktorial von n - 1 (dies ist unser rekursiver Fall).

So wird factorial(5) zu: 5 factorial(4) 5 (4 factorial(3)) 5 (4 (3 factorial(2))) 5 (4 (3 (2 factorial(1)))) 5 (4 (3 (2 1))) 5 4 3 2 1 = 120

Die Macht der Rekursion

Rekursion kann einige komplexe Probleme viel einfacher zu lösen machen. Lassen Sie uns ein etwas fortgeschritteneres Beispiel anschauen: die Fibonacci-Folge.

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

for i in range(10):
print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34

Diese Funktion berechnet die nth Fibonacci-Zahl. Die Fibonacci-Folge beginnt mit 0 und 1, und jede folgende Zahl ist die Summe der beiden vorherigen.

Binäre Suche mit Rekursion

Nun erledigen wir ein praktischeres Beispiel: die binäre Suche. Dies ist eine effiziente Methode, um ein Element in einer sortierten Liste zu finden.

def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2

if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1

arr = [2, 3, 4, 10, 40]
x = 10

result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:
print(f"Element ist bei Index {result} vorhanden")
else:
print("Element ist nicht in Array vorhanden")

Diese Funktion funktioniert, indem sie wiederholt das Suchintervall durch Halbierung verkleinert. Wenn der Wert des Suchschlüssels kleiner ist als das Element in der Mitte des Intervalls, verengen Sie das Intervall auf die untere Hälfte. Andernfalls verengen Sie es auf die obere Hälfte. Wiederholen Sie die Überprüfung, bis der Wert gefunden wird oder das Intervall leer ist.

Wann Rekursion verwenden

Rekursion ist besonders nützlich für:

1. Probleme, die in ähnliche Unterprobleme aufgeteilt werden können
2. Baumartige Datenstrukturen (z.B. Dateisysteme, HTML DOM)
3. Algorithmen wie QuickSort, MergeSort usw.

Allerdings ist Rekursion nicht immer die beste Lösung. Sie kann für sehr tiefe Rekursionen speicherintensiv sein, und manchmal kann eine einfache Schleife effizienter und leichter zu verstehen sein.

Tabelle der Rekursionsmethoden

Methode	Beschreibung	Beispiel
Direkte Rekursion	Eine Funktion ruft sich selbst direkt auf	Unsere countdown- und factorial-Beispiele
Indirekte Rekursion	Funktion A ruft Funktion B auf, die dann Funktion A ruft	Siehe Beispiel unten
Schwanzrekursion	Der rekursive Aufruf ist das Letzte, was von der Funktion ausgeführt wird	Unsere countdown-Beispiel
Nicht-Schwanzrekursion	Der rekursive Aufruf ist nicht das Letzte, was von der Funktion ausgeführt wird	Unsere factorial-Beispiel

Hier ist ein Beispiel für indirekte Rekursion:

def ist_gleich(n):
if n == 0:
return True
else:
return ist_ungerade(n - 1)

def ist_ungerade(n):
return not ist_gleich(n)

print(ist_gleich(4))  # Output: True
print(ist_ungerade(4)) # Output: False

In diesem Beispiel ruft ist_gleich ist_ungerade auf, welches dann ist_gleich ruft.

Fazit

Herzlichen Glückwunsch! Sie haben gerade Ihre ersten Schritte in die faszinierende Welt der Rekursion gemacht. Erinnern Sie sich, wie jedes leistungsstarke Werkzeug, Rekursion weise verwendet werden sollte. Sie kann Ihren Code eleganter machen und komplexe Probleme mit Leichtigkeit lösen, aber sie kann auch einfache Probleme unnötig kompliziert machen.

Während Sie Ihren Python-Weg fortsetzen, werden Sie viele weitere Situationen erleben, in denen Rekursion angewendet werden kann. Üben Sie weiter und bald werden Sie wie ein Profi rekursieren!

Credits: Image by storyset