Python Rekursives Funktionskonzept: Python-Tutorial für Anfänger

In der Welt der Informatik bezieht sich Rekursion auf die Technik, eine Sache in ihren eigenen Begriffen zu definieren. Mit anderen Worten, eine rekursive Funktion ruft sich selbst zur Verarbeitung auf. In diesem Artikel werden wir das Konzept der rekursiven Funktion in Python verstehen , einer weit verbreiteten Programmiersprache des 21. Jahrhunderts.

Was ist Python-Rekursion ?

In Python wird eine Gruppe verwandter Anweisungen, die eine bestimmte Aufgabe ausführen, als „Funktion“ bezeichnet. Funktionen unterteilen Ihr Programm also in kleinere Teile. Und es ist allgemein bekannt, dass eine Funktion andere Funktionen in Python aufrufen kann.

Aber einige andere Funktionen können sich selbst aufrufen. Diese werden als rekursive Funktionen bezeichnet. Stellen Sie sich zwei parallele Spiegel vor, die einander zugewandt angeordnet sind. Nun würde jedes Objekt, das zwischen den Spiegeln gehalten wird, rekursiv reflektiert werden.

Lassen Sie uns detailliert auf die rekursive Funktion eingehen, um ihre Funktionsweise klar zu verstehen.

Die rekursive Funktion

Wir wissen, dass sich eine rekursive Funktion in Python so aufruft, wie sie über selbstreferenzielle Ausdrücke definiert ist, dh in Bezug auf sich selbst. Es wiederholt sein Verhalten so lange, bis eine bestimmte Bedingung erfüllt ist, um einen Wert oder ein Ergebnis zurückzugeben. Sehen wir uns nun ein Beispiel an, um zu erfahren, wie es funktioniert.

Lesen Sie auch: Fragen und Antworten zu Python-Interviews

Angenommen, Sie möchten die Fakultät einer ganzen Zahl ermitteln. Fakultät ist nichts anderes als das Produkt aller Zahlen, beginnend bei 1 bis zu dieser ganzen Zahl. Zum Beispiel wäre die Fakultät von 5 (geschrieben als 5!) 1*2*3*4*5*6, also 720. Wir haben eine rekursive Funktion calc_factorial(x), die wie folgt definiert ist:

def Berechnungsfaktor(x):

#Rekursive Funktion, um die Fakultät einer ganzen Zahl zu finden

wenn x == 1:

Rückkehr 1

anders

return (x * calc_factorial(x-1))

Was würde passieren, wenn Sie diese Funktion mit einer positiven Ganzzahl wie 4 aufrufen? Nun, jeder Funktionsaufruf fügt einen Stapelrahmen hinzu, bis wir den Basisfall erreichen (wenn sich die Zahl auf 1 reduziert). Die Basisbedingung ist erforderlich, damit die Rekursion endet und nicht unendlich weitergeht. Im gegebenen Fall wird also nach dem vierten Aufruf der Wert 24 zurückgegeben.

Implementierung der rekursiven Funktion in Python

Es kann vielfältige Anwendungen von rekursiven Funktionen in Python geben. Sie möchten beispielsweise eine Grafik mit einem sich wiederholenden Muster erstellen, sagen wir eine Koch-Schneeflocke. Rekursion kann zum Generieren von Fraktalmustern verwendet werden, die aus kleineren Versionen desselben Designs bestehen.

Ein weiteres Beispiel ist das Lösen von Spielen. Sie können rekursive Algorithmen zum Lösen von Sudoku und zahlreichen komplexen Spielen schreiben. Rekursion wird am häufigsten beim Suchen, Sortieren und Durchlaufen von Problemen verwendet.

Auffallend an der Funktion ist, dass die rekursive Implementierung ein Backtracking erlaubt. Bei der Rekursion geht es also darum, eine Lösung schrittweise zu erstellen und diejenigen Lösungen zu entfernen, die die Problembeschränkungen zu keinem Zeitpunkt erfüllen. Um dies zu erreichen, sind zwei Dinge notwendig – die Aufrechterhaltung des Zustands und eine geeignete Datenstruktur. Lesen Sie weiter, um sich mit diesen Begriffen vertraut zu machen.

Lesen Sie: Python-Entwicklergehalt in Indien

Staat erhalten

Jeder rekursive Aufruf in Python hat seinen eigenen Ausführungskontext. Beim Umgang mit rekursiven Funktionen in Python müssen Sie den Zustand durch jeden rekursiven Aufruf führen. Damit wird der aktuelle Zustand Teil des Ausführungskontextes des aktuellen Aufrufs. Sie können den Zustand auch im globalen Geltungsbereich behalten.

Wenn Sie beispielsweise die Rekursion verwenden, um 1+2+3+4+…….+10 zu berechnen. Hier bilden die aktuelle Zahl, die Sie addieren, und die bis dahin akkumulierte Summe den Zustand, den Sie beibehalten müssen. Das Aufrechterhalten des Zustands beinhaltet das Weiterleiten des aktualisierten aktuellen Zustands als Argumente durch jeden Aufruf. Hier ist, wie Sie es tun können.

def Summenzahlen(aktuelle_Zahl, kumulierte_Summe)

#Basisfall

#Endzustand zurückgeben

wenn aktuelle Zahl==11:

akkumulierte_summe zurückgeben

#Rekursiver Fall

#Thread den Zustand durch rekursiven Aufruf

Anders:

return sum_numbers(aktuelle_Zahl + 1, kumulierte_Summe + aktuelle_Zahl)

Alternativ können Sie den global änderbaren Zustand verwenden. Um den Zustand mit dieser Methode beizubehalten, belassen Sie den Zustand im globalen Bereich.

aktuelle_nummer = 1

akkumulierte_summe = 0

def Summenzahlen():

globale aktuelle_nummer

globale akkumulierte_summe

#Basisfall

wenn aktuelle_nummer==11

akkumulierte_summe zurückgeben

#Rekursiver Fall

anders:

kumulierte_Summe = kumulierte_Summe + aktuelle_Zahl

aktuelle_nummer = aktuelle_nummer + 1

Summe_Zahlen() zurückgeben

Rekursive Datenstrukturen

Eine Datenstruktur wird als rekursiv angesehen, wenn sie in Bezug auf kleinere und einfachere Versionen ihrer selbst definiert werden kann. Beispiele für rekursive Datenstrukturen sind Listen, Bäume, hierarchische Strukturen, Wörterbücher usw. Eine Liste kann andere Listen als Elemente haben. Ein Baum hat Unterbäume, Blattknoten und so weiter.

Es ist wichtig, hier zu beachten, dass die Struktur rekursiver Funktionen oft nach den Datenstrukturen modelliert wird, die sie als Eingaben verwendet. Rekursive Datenstrukturen und rekursive Funktionen gehen also Hand in Hand.

Rekursion in der Fibonacci-Berechnung

Der italienische Mathematiker Fibonacci definierte erstmals im 13. Jahrhundert die Fibonacci-Zahlen, um das Bevölkerungswachstum von Kaninchen zu modellieren. Er folgerte, dass ausgehend von einem Kaninchenpaar im ersten Jahr die Anzahl der in einem bestimmten Jahr geborenen Kaninchenpaare der Anzahl der in jedem der letzten beiden Jahre geborenen Kaninchenpaare entspricht. Dies kann geschrieben werden als: Fn = Fn-1 + Fn-2 (Basisfälle: F0=1 und F1=1).

Wenn Sie eine rekursive Funktion schreiben, um die Fibonacci-Zahl zu berechnen, kann dies zu einer naiven Rekursion führen. Dies passiert, wenn die Definition der rekursiven Funktion naiv befolgt wird und Sie am Ende unnötigerweise Werte neu berechnen. Um eine Neuberechnung zu vermeiden, können Sie den lru_cache-Dekorator auf die Funktion anwenden. Es speichert die Ergebnisse im Cache und verhindert, dass der Prozess ineffizient wird.

Weiterlesen: Top 10 Python-Tools, die jeder Python-Entwickler kennen sollte

Vor- und Nachteile von Rekursiv

Rekursion hilft, eine komplexe Aufgabe zu vereinfachen, indem sie in Teilprobleme aufgeteilt wird. Rekursive Funktionen sorgen für saubereren Code und vereinfachen auch die Generierung von Sequenzen. Aber die Rekursion kommt nicht ohne ihre Einschränkungen. Manchmal können sich die Aufrufe als teuer und ineffizient erweisen, da sie viel Zeit und Speicherplatz verbrauchen. Rekursive Funktionen können auch schwierig zu debuggen sein.

Einpacken

In diesem Artikel haben wir das Konzept der Python-Rekursion behandelt , es anhand einiger Beispiele demonstriert und auch einige seiner Vor- und Nachteile diskutiert. Mit all diesen Informationen können Sie in Ihrem nächsten Python-Interview problemlos rekursive Funktionen erklären!

Wenn Sie neugierig sind, mehr über Data Science zu erfahren, schauen Sie sich das PG Diploma in Data Science von IIIT-B & upGrad an, das für Berufstätige entwickelt wurde und mehr als 10 Fallstudien und Projekte, praktische Workshops, Mentoring mit Branchenexperten, 1- on-1 mit Mentoren aus der Branche, mehr als 400 Stunden Lern- und Jobunterstützung bei Top-Unternehmen.