In diesem Tutorial lernen Sie, eine rekursive Funktion zu erstellen (eine Funktion, die sich selbst aufruft).
Was ist Rekursion?
Rekursion ist der Prozess, etwas in Bezug auf sich selbst zu definieren.
Ein Beispiel für eine physikalische Welt wäre, zwei parallele Spiegel einander gegenüberzustellen. Jedes Objekt dazwischen würde rekursiv reflektiert.
Rekursive Python-Funktion
In Python wissen wir, dass eine Funktion andere Funktionen aufrufen kann. Es ist sogar möglich, dass sich die Funktion selbst aufruft. Diese Arten von Konstrukten werden als rekursive Funktionen bezeichnet.
Das folgende Bild zeigt die Arbeitsweise einer aufgerufenen rekursiven Funktion recurse.
Rekursive Funktion in Python
Es folgt ein Beispiel für eine rekursive Funktion zum Ermitteln der Fakultät einer Ganzzahl.
Das Faktorielle einer Zahl ist das Produkt aller ganzen Zahlen von 1 bis zu dieser Zahl. Zum Beispiel ist die Fakultät von 6 (bezeichnet als 6!) 1 * 2 * 3 * 4 * 5 * 6 = 720.
Beispiel einer rekursiven Funktion
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Ausgabe
Die Fakultät von 3 ist 6
Im obigen Beispiel factorial()handelt es sich um eine rekursive Funktion, wie sie sich selbst aufruft.
Wenn wir diese Funktion mit einer positiven Ganzzahl aufrufen, ruft sie sich rekursiv auf, indem sie die Zahl verringert.
Jede Funktion multipliziert die Zahl mit der Fakultät der Zahl darunter, bis sie gleich eins ist. Dieser rekursive Aufruf kann in den folgenden Schritten erläutert werden.
Fakultät (3) # 1. Anruf mit 3 3 * Fakultät (2) # 2. Anruf mit 2 3 * 2 * Fakultät (1) # 3. Anruf mit 1 3 * 2 * 1 # Rückkehr vom 3. Anruf als Nummer = 1 3 * 2 # Rückkehr vom 2. Anruf 6 # Rückkehr vom 1. Anruf
Schauen wir uns ein Bild an, das Schritt für Schritt zeigt, was vor sich geht:
Arbeiten einer rekursiven Fakultätsfunktion
Unsere Rekursion endet, wenn sich die Zahl auf 1 verringert. Dies wird als Grundbedingung bezeichnet.
Jede rekursive Funktion muss eine Grundbedingung haben, die die Rekursion stoppt, sonst ruft sich die Funktion unendlich auf.
Der Python-Interpreter begrenzt die Tiefe der Rekursion, um unendliche Rekursionen zu vermeiden, die zu Stapelüberläufen führen.
Standardmäßig beträgt die maximale Rekursionstiefe 1000. Wenn das Limit überschritten wird, führt dies zu RecursionError. Schauen wir uns eine solche Bedingung an.
def recursor(): recursor() recursor()
Ausgabe
Rückverfolgung (letzter Aufruf zuletzt): Datei "", Zeile 3, in Datei "", Zeile 2, in einer Datei "", Zeile 2, in einer Datei "", Zeile 2, in einer (vorherige Zeile 996 weitere Male wiederholt ) RecursionError: Maximale Rekursionstiefe überschritten
Vorteile der Rekursion
- Rekursive Funktionen lassen den Code sauber und elegant aussehen.
- Eine komplexe Aufgabe kann mithilfe der Rekursion in einfachere Unterprobleme unterteilt werden.
- Die Sequenzgenerierung ist mit der Rekursion einfacher als mit einer verschachtelten Iteration.
Nachteile der Rekursion
- Manchmal ist die Logik hinter der Rekursion schwer zu befolgen.
- Rekursive Anrufe sind teuer (ineffizient), da sie viel Speicher und Zeit in Anspruch nehmen.
- Rekursive Funktionen sind schwer zu debuggen.
