Rekursion
Beim Programmieren lernen wir oft, Aufgaben auf lineare, direkte Weise anzugehen. Aber was ist, wenn wir auf ein Problem stoßen, das erfordert, es in kleinere, ähnliche Probleme zu zerlegen? Hier kommt die Rekursion ins Spiel.
Einfach ausgedrückt ist Rekursion, wenn eine Funktion sich während ihrer Ausführung selbst aufruft. Das mag nach einer Endlosschleife klingen, aber wenn wir unsere Funktion richtig gestalten, erreicht sie schließlich einen Punkt, an dem sie sich nicht mehr selbst aufruft.
Stellen Sie sich eine Matroschka-Puppe vor. Jedes Mal, wenn Sie eine Puppe öffnen, befindet sich eine kleinere darin, und Sie setzen diesen Vorgang fort, bis Sie die kleinste Puppe erreichen, die nicht geöffnet werden kann. Dieser Prozess des Öffnens von Puppen ähnelt der Rekursion. Um die kleinste Puppe zu erreichen, was dem Lösen des schwierigsten Problems entspricht, lösen Sie es, indem Sie wiederholt einfachere Versionen desselben Problems lösen (die größeren Puppen öffnen), bis Sie einen Punkt erreichen, an dem das Problem nicht weiter vereinfacht werden kann (die letzte Puppe).
Der Prozess, ein großes Problem zu lösen, indem man es rekursiv in kleinere Probleme aufteilt, bis man das kleinste/möglichst einfachste erreicht, wird am besten mit dem Konzept des „rekursiven Vertrauenssprungs“ verstanden.
Rekursiver Vertrauenssprung
Bei der Umsetzung einer rekursiven Lösung für ein Problem erstellt man in der Regel eine Funktion, die sich an irgendeinem Punkt selbst aufruft. Der Teil, in dem sie sich selbst aufruft, wird oft als der rekursive Aufruf bezeichnet.
Der große Vorteil rekursiver Lösungen ist, dass man annehmen kann, dass die Funktion korrekt funktioniert, wenn sie mit einigen einfachen Argumenten aufgerufen wird, und dann das korrekte Verhalten für die schwierigeren implementieren kann. Ähnlich wie bei Aufrufen anderer Funktionen wie
sqrt, max, abs und anderen, die wir zuvor verwendet haben, können Sie annehmen, dass die Funktion für kleinere/einfachere Argumente funktioniert und diese aufrufen, um das aktuelle Ergebnis darauf aufzubauen.💡
Die einzige Voraussetzung ist sicherzustellen, dass die Funktion den Basisfall (den einfachsten Fall) erreicht. Andernfalls hätten wir eine unendlich laufende rekursive Funktion und könnten einen StackOverflow bekommen!
Als Demonstration, wie man eine Berechnung innerhalb einer rekursiven Funktion durchführen kann, können wir versuchen, die Summe aller Zahlen von
0, 1, 2, …, n für eine gegebene Zahl n zu berechnen.Lassen Sie uns die
sum-Funktion Schritt für Schritt implementieren. Der erste Schritt besteht darin, sicherzustellen, dass die Funktion für den einfachsten Fall korrekt funktioniert (die Summe für n gleich 0 oder 1 richtig berechnet):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0: # Falls n 0 ist => die Summe ist 0
return 0 # Beendet die Funktion hier
if n == 1: # Falls n 1 ist => die Summe ist 1
return 1 # Beendet die Funktion hier
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> None (da wir diesen Teil noch nicht implementiert haben)Mit diesem Teil der Funktion können wir bereits die Tatsache nutzen, dass
sum(0) immer korrekt 0 zurückgibt, während sum(1) immer 1 zurückgibt. Die Funktion wird korrekt funktionieren, selbst wenn wir die sum-Funktion mit den Argumenten 0 oder 1 aus der sum-Funktion selbst aufrufen.Wir können also einen Schritt weiter gehen und die
sum-Funktion für n = 2 und n = 3 implementieren, indem wir die Ergebnisse für sum(1) und sum(0) verwenden:def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2: # Wenn n 2 ist, können wir 2 zum Ergebnis von sum(1) addieren, das oben implementiert wurde
return n + sum(1) # oder n + sum(n - 1)
if n == 3: # Wenn n 3 ist, können wir 3 zum Ergebnis von sum(2) addieren, das oben implementiert wurde
return n + sum(2) # oder n + sum(n - 1)
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> None (da wir diesen Teil noch nicht implementiert haben)Auf diese Weise ist es offensichtlich, dass die
sum-Funktion für kleine Fälle wie n gleich 0, 1, 2 oder 3 korrekt funktioniert.Damit können wir die Funktion für andere Werte von
n größer als 3 implementieren. Die einzige Voraussetzung ist, dass wir zu diesen kleineren Werten von n (0, 1, 2 oder 3) gelangen, wenn wir die Funktion sum aus sich selbst aufrufen. Für größere Werte von n, wie 4, 5 oder 6 usw., können wir die sum-Funktion implementieren, indem wir die Tatsache nutzen, dass wir zur Berechnung von sum(4) 4 zum Ergebnis von sum(3) addieren können, während die Berechnung von sum(5) durch das Addieren von 5 zum Ergebnis von sum(4) erfolgen kann:def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return n + sum(1)
if n == 3:
return n + sum(2)
# Für alle anderen Fälle (4, 5, 6, ...)
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...Die Schlüsselelemente einer rekursiven Funktion sind:
- Basisfall: Eine Bedingung, die die Rekursion stoppt. Ohne diese würde die Funktion sich unendlich oft selbst aufrufen und eine Endlosschleife verursachen.
Hier sind es
n == 0undn == 1.
- Rekursiver Schritt: Hier ruft die Funktion sich selbst auf, normalerweise mit einem anderen Argument.
Hier ist es
sum(n - 1).
Da die Aufrufe für
n == 1, n == 2 und n == 3 genau die gleichen sind wie für n == 4, n == 5 usw., können wir die sum-Funktion sogar vereinfachen, indem wir nur einen Basisfall haben (für n == 0):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...Auf diese Weise vertrauen wir im rekursiven Vertrauenssprung darauf, dass die Funktion für kleinere/einfachere Fälle korrekt funktioniert, und konstruieren den Rest der Funktion basierend auf diesen einfacheren Fällen. Das hilft dabei zu verstehen, wie rekursive Funktionen funktionieren und wie sie implementiert werden können.
💡
Das rekursive Aufrufen der Funktion ist wie das Aufrufen einer völlig anderen Funktion, von der Sie mit Sicherheit wissen, dass sie mit den übergebenen Argumenten funktioniert.