Python-Rekursion

In diesem Tutorial lernen Sie, eine rekursive Funktion (eine Funktion, die sich selbst aufruft) zu erstellen.

Was ist Rekursion?

Rekursion ist der Prozess, etwas durch sich selbst zu definieren.

Ein Beispiel aus der physikalischen Welt wäre, zwei parallele Spiegel einander gegenüber zu platzieren. Jedes Objekt dazwischen würde rekursiv reflektiert werden.

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 Funktionsweise einer rekursiven Funktion namens recurse .

Es folgt ein Beispiel einer rekursiven Funktion, um die Fakultät einer ganzen Zahl zu finden.

Die Fakultät einer Zahl ist das Produkt aller ganzen Zahlen von 1 bis zu dieser Zahl. Beispielsweise ist die Fakultät von 6 (als 6 bezeichnet!) 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

The factorial of 3 is 6

Im obigen Beispiel factorial() ist eine rekursive Funktion, wie sie sich selbst aufruft.

Wenn wir diese Funktion mit einer positiven Ganzzahl aufrufen, ruft sie sich rekursiv selbst 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.

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Sehen wir uns ein Bild an, das Schritt für Schritt zeigt, was vor sich geht:

Unsere Rekursion endet, wenn die Zahl auf 1 reduziert wird. Dies wird als Basisbedingung bezeichnet.

Jede rekursive Funktion muss eine Grundbedingung haben, die die Rekursion stoppt, sonst ruft sich die Funktion endlos selbst auf.

Der Python-Interpreter begrenzt die Rekursionstiefe, um unendliche Rekursionen zu vermeiden, die zu Stapelüberläufen führen.

Standardmäßig beträgt die maximale Rekursionstiefe 1000 . Wird die Grenze überschritten, ergibt sich RecursionError . Sehen wir uns eine solche Bedingung an.

def recursor():
    recursor()
recursor()

Ausgabe

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Vorteile der Rekursion

Rekursive Funktionen lassen den Code sauber und elegant aussehen.
Eine komplexe Aufgabe kann mithilfe von Rekursion in einfachere Teilprobleme zerlegt werden.
Die Generierung von Sequenzen ist mit Rekursion einfacher als mit einer verschachtelten Iteration.

Nachteile der Rekursion

Manchmal ist die Logik hinter der Rekursion schwer nachzuvollziehen.
Rekursive Aufrufe sind teuer (ineffizient), da sie viel Speicherplatz und Zeit beanspruchen.
Rekursive Funktionen sind schwer zu debuggen.

Python-Funktionsargumente Anonyme Python/Lambda-Funktion

Python