Was ist eine rekursive Funktion?
Funktion ruft sich immer wieder auf, bis sie eine rekursive Bedingung erfüllt. Eine Rekursionsfunktion unterteilt das Problem in kleinere Probleme und ruft eine eigene Logik auf, um das kleinere Problem zu lösen. Diese Technik wird als Teilen und Erobern bezeichnet. Es wird in der Mathematik und der Informatik verwendet.
Die rekursive Funktion umfasst einen Basisfall (oder Endfall) und einen rekursiven Fall. Im Basisfall können Sie das zu lösende Hauptproblem betrachten, und der rekursive Fall unterteilt das Problem in kleinere Teile, bis es eine Ebene erreicht, in der es leicht gelöst werden kann. Ein rekursiver Fall kann ein Ergebnis zurückgeben oder sich selbst erneut aufrufen, um das Problem weiter zu unterteilen. Jedes Mal, wenn das Problem in kleinere Probleme zerfällt, speichert die Funktion, die rekursiv aufgerufen wird, den Status des Aufrufs und erwartet das Ergebnis von sich selbst, nachdem das Problem aufgelöst wurde.
Rekursive Funktion in Python
Das Konzept der Rekursion bleibt in Python dasselbe. Die Funktion ruft sich selbst auf, um das Problem in kleinere Probleme aufzuteilen. Das einfachste Beispiel für eine Rekursion wäre das Ermitteln der Fakultät einer Zahl.
Nehmen wir an, wir müssen die Fakultät der Zahl 5 => 5 finden! (Unser Problem)
5 zu finden! Das Problem kann in kleinere 5 unterteilt werden! => 5 x 4!
Also, um 5 zu bekommen! Wir müssen 4 finden! und mit 5 multiplizieren.
Teilen wir das Problem weiter auf
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Wenn es den kleinsten Teil erreicht, dh die Fakultät von 1, können wir das Ergebnis als zurückgeben
Nehmen wir ein Pseudocode-Beispiel:
Algorithmus für Fakultät
Sehen wir uns den Algorithmus für Fakultät an:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Funktionsaufrufe
Angenommen, wir finden eine Fakultät von 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
Das Endergebnis wird 120 sein, wo wir die Ausführung der Funktion gestartet haben. Unsere Rekursionsfunktion wird beendet, wenn die Anzahl so verringert wird, dass das Ergebnis erhalten werden kann.
- Der erste Aufruf, der die Fakultät 5 erhält, führt zu einer rekursiven Bedingung, bei der er dem Stapel hinzugefügt wird und ein weiterer Aufruf erfolgt, nachdem die Zahl auf 4 reduziert wurde.
- Diese Rekursion ruft das Problem weiterhin auf und teilt es in kleinere Abschnitte auf, bis die Grundbedingung erreicht ist.
- Die Grundbedingung ist hier, wenn die Zahl 1 ist.
- Jede rekursive Funktion hat eine eigene rekursive Bedingung und eine Grundbedingung.
Vor- und Nachteile der rekursiven Python-Funktion
- Die Ausführung der Rekursion erfolgt so, dass bis zum Erreichen der Grundbedingung keine Berechnungen durchgeführt werden.
- Bei Erreichen der Grundbedingungen kann Ihnen der Speicher ausgehen.
- Bei einem großen Problem, bei dem es eine Million Schritte oder eine Million Rekursionen für das Programm geben kann, kann dies zu Speicherfehlern oder Segmentierungsfehlern führen.
- 1000000! = 1000000 * 999999! =?
- Rekursion unterscheidet sich von Iteration und lässt sich nicht wie eine iterative Methode skalieren.
- Unterschiedliche Sprachen haben unterschiedliche Optimierungen für die Rekursion.
- In vielen Sprachen ist die iterative Methode leistungsfähiger als die Rekursion.
- Jede Sprache hat einige Einschränkungen hinsichtlich der Rekursionstiefe, die bei der Lösung großer Probleme auftreten können.
- Manchmal ist es schwierig, die komplexen Probleme mit der Rekursion zu verstehen, während es mit der Iteration ziemlich einfach ist.
Einige Profis
- In einigen Fällen ist die Rekursion eine bequeme und schnellere Methode.
- Sehr nützlich beim Durchlaufen des Baums und der binären Suche.
Python-Code - Rekursion vs. Iteration
Wir haben verstanden, was Rekursion ist und wie sie in Python funktioniert, da wir wissen, dass alle Sprachen die Rekursion für Speicher- und Rechenoptimierungen unterschiedlich implementieren. Es kann vorkommen, dass die Iteration schneller ist als die Rekursion.
Hier würden wir sowohl die Rekursions- als auch die Iterationsmethode vergleichen, um zu sehen, wie Python in beiden Fällen funktioniert.
1. Rekursionscode für Factorial
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Faktorielles Problem bei der Iteration (Schleifen)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Ergebnisse drucken
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Ausgabe:
Wie wir sehen können, geben beide die gleiche Ausgabe aus, wie wir die gleiche Logik geschrieben haben. Hier sehen wir keinen Unterschied in der Ausführung.
Fügen wir etwas Zeitcode hinzu, um weitere Informationen zur Ausführung von Rekursion und Iteration in Python zu erhalten.
Wir werden die "Zeit" -Bibliothek importieren und prüfen, wie lange die Rekursion und Iteration dauert, um das Ergebnis zurückzugeben.
4. Code mit Zeitberechnung
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Wir werden wiederholte Ausführungen mit einem anderen Wert für Fakultät durchführen und die Ergebnisse sehen. Die folgenden Ergebnisse können von Maschine zu Maschine variieren. Wir haben MacBook Pro 16 GB RAM i7 verwendet.
Wir verwenden Python 3.7 zur Ausführung
Fall 1: - Faktoriell von 6:
Fall 2: Faktor von 50:
Fall 3: Faktor 100:
Fall 4: Faktor von 500:
Fall 5: Faktor von 1000:
Wir haben beide Methoden in einem unterschiedlichen Problem analysiert. Darüber hinaus haben beide mit Ausnahme von Fall 4 ähnliche Ergebnisse erzielt.
In Fall 5 ist ein Fehler bei der Rekursion aufgetreten.
Python hat eine Beschränkung für die maximale Tiefe, die Sie mit der Rekursion erreichen können, aber das gleiche Problem, das ich mit Iteration lösen konnte.
Python hat Einschränkungen gegen das Problem des Überlaufs. Python ist nicht für die Schwanzrekursion optimiert, und eine unkontrollierte Rekursion führt zu einem Stapelüberlauf.
Die Funktion "sys.getrecursionlimit ()" gibt die Grenze für die Rekursion an.
Das Rekursionslimit kann geändert werden, es wird jedoch nicht empfohlen, es könnte gefährlich sein.
Schlussfolgerung - Rekursive Python-Funktion
- Rekursion ist eine praktische Lösung für einige Probleme wie das Durchlaufen von Bäumen und andere.
- Python ist keine funktionierende Programmiersprache, und wir können sehen, dass der Rekursionsstapel im Vergleich zur Iteration nicht so optimiert ist.
- Wir sollten die Iteration in unserem Algorithmus verwenden, da sie in Python optimiert ist und Ihnen eine bessere Geschwindigkeit verleiht.
Empfohlene Artikel
Dies ist eine Anleitung zur rekursiven Funktion in Python. Hier besprechen wir, was rekursive Funktion, rekursive Funktion in Python, Algorithmus für Fakultät usw. ist. Sie können auch unsere anderen vorgeschlagenen Artikel durchgehen, um mehr zu erfahren.
- Fakultät in Python
- Spark-Shell-Befehle
- Beste C-Compiler
- Arten von Algorithmen
- Factorial-Programm in JavaScript
- Leitfaden zur Liste der Unix-Shell-Befehle
- Arten von Formen reagieren mit Beispielen