Python Recursion

Table of Contents

 

In diesem Tutorial erfahren Sie, wie Sie eine rekursive Funktion 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.

 

 

 

Python Rekursive 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.

Recursive Function in Python
Rekursive Funktion in Python

 

Es folgt ein Beispiel für eine rekursive 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. Zum Beispiel ist die Fakultät von 6 (als 6 bezeichnet!)

1*2*3*4*5*6 = 720

 

Beispiel für eine rekursive Funktion

def factorial(x):
    """Dies ist eine rekursive Funktion
    um die Fakultät einer ganzen Zahl zu finden"""

    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))


num = 3
print("Die Fakultät von", num, "ist", factorial(num))

 

Output

Die Fakultät von 3 ist 6

 

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

Wenn wir diese Funktion mit einer positiven ganzen Zahl aufrufen, ruft sie sich selbst rekursiv auf, indem sie die Zahl verringert.

Jede Funktion multipliziert die Zahl mit der Fakultät der darunter liegenden Zahl, bis sie gleich eins ist. Dieser rekursive Aufruf kann in den folgenden Schritten erklärt 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

 

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

Working of a recursive factorial function
Arbeiten einer rekursiven Faktor Funktion

 

 

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

Jede rekursive Funktion muss eine Basisbedingung haben, die die Rekursion stoppt oder die Funktion ruft sich selbst unendlich auf.

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

 

Standardmäßig beträgt die maximale Rekursionstiefe 1000. Wenn die Grenze überschritten wird, führt dies zu RecursionError. Schauen wir uns eine solche Bedingung an.

 

def recursor():
    recursor()
recursor()

 

Output

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

  1. Rekursive Funktionen lassen den Code sauber und elegant aussehen.
  2. Eine komplexe Aufgabe kann mittels Rekursion in einfachere Teilprobleme zerlegt werden.
  3. Die Sequenzgenerierung ist mit Rekursion einfacher als mit einer verschachtelten Iteration.

 

Nachteile der Rekursion

 

  1. Manchmal ist die Logik hinter der Rekursion schwer zu durchschauen.
  2. Rekursive Aufrufe sind teuer (ineffizient), da sie viel Speicher und Zeit beanspruchen.
  3. Rekursive Funktionen sind schwer zu debuggen.