Was ist Rekursion?

Rekursion ist der Prozess der Definition von etwas in Bezug auf sich selbst.

Ein Beispiel für die physische 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 Konstrukttypen werden als rekursive Funktionen bezeichnet.

Das folgende Bild zeigt die Funktionsweise einer rekursiven Funktion namens recurse.

Im Folgenden finden Sie ein Beispiel für eine rekursive Funktion zum Ermitteln der Fakultät einer Ganzzahl.

Die Fakultät einer Zahl ist das Produkt aller ganzen Zahlen von 1 bis zu dieser Zahl. Zum Beispiel die Fakultät von 6 (bezeichnet als 6!) ist 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 = 3print("The factorial of", num, "is", factorial(num))

Ausgabe

The factorial of 3 is 6

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

Wenn wir diese Funktion mit einer positiven ganzen Zahl aufrufen, ruft sie sich 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 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call

Schauen 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 Basisbedingung 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 der Grenzwert überschritten wird, führt dies zu RecursionError. Schauen 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 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 der Rekursion einfacher als mit einer verschachtelten Iteration.

Nachteile der Rekursion

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