Was ist Rekursion und wie verwenden Sie sie?

Eskere Guru

Rekursion ist ein unterhaltsames Programmierkonzept, das jedoch etwas schwierig zu erlernen ist. Rekursion bedeutet einfach etwas, das sich wiederholt. Wenn Sie ein freches Beispiel für Rekursion sehen möchten, suchen Sie bei Google nach Rekursion . Sie finden ein Osterei, in dem die Vorschläge für Suchergebnisse rekursiv sind. Wenn Sie andererseits lernen möchten, wie man eine rekursive Funktion codiert, lesen Sie weiter!

Was ist eine rekursive Funktion?

Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft. Sie erstellen im Wesentlichen eine Schleife mit einer Funktion. Wie Sie sich vorstellen können, können diese Funktionen schwierig zu schreiben sein. Sie möchten nicht, dass Ihr Code für immer ausgeführt wird.

Ähnlich wie bei einer Schleife wird eine rekursive Funktion durch eine Bedingung gesteuert. Sobald die Bedingung erfüllt ist, hört die Funktion auf, sich selbst aufzurufen, wodurch die Schleife gestoppt wird. Auf diese Weise können Sie eine Funktion erstellen, die sich selbst aufruft, ohne dass sie für immer ausgeführt wird.

Obwohl eine rekursive Funktion wie eine Schleife wirkt, wird sie vom Computer anders ausgeführt. Einige Algorithmen sind in einer Schleife effizienter, andere profitieren von einer rekursiven Funktion. Bevor wir uns jedoch mit der Verwendung einer rekursiven Funktion befassen, müssen Sie wissen, wie man eine schreibt.

So schreiben Sie eine rekursive Funktion

Alle rekursiven Funktionen haben die gleiche Grundstruktur:

 FUNCTION name
 IF condition THEN
 RETURN result
 ELSE
 CALL FUNCTION name
 END FUNCTION

Das obige Beispiel ist in Pseudocode geschrieben. Es beschreibt die Struktur der Funktion, die auf jede Sprache angewendet werden kann. Der Einfachheit halber konzentrieren wir uns in diesem Artikel auf Python.

Das Erste, was bei einer rekursiven Funktion zu beachten ist, ist, dass die Funktion die Rekursion verlässt, wenn die Bedingung erfüllt ist. Wenn Sie also eine rekursive Funktion schreiben, müssen Sie zunächst festlegen, wann die Rekursion gestoppt werden soll.

Wenn die Bedingung nicht erfüllt ist, ruft sich die Funktion selbst auf. Wenn Sie also Informationen an die nächste Schleife senden möchten, müssen Sie diese als Argument in Ihrer Funktion senden. Dies kann rekursiven Funktionen viel mehr Leistung verleihen.

Verwandte: Was ist eine Funktion in der Programmierung?

Beispiel für eine rekursive Funktion in Python

Es ist viel einfacher zu verstehen, wie Rekursion funktioniert, wenn Sie sie in Aktion sehen. Um dies zu demonstrieren, schreiben wir eine rekursive Funktion, die die Fakultät einer Zahl zurückgibt.

Fakultäten geben das Produkt einer Zahl und aller davor stehenden ganzen Zahlen zurück. Zum Beispiel ist die Fakultät von 5 5 × 4 × 3 × 2 × 1 oder 120.

 def factorialFunction(numberToMultiply):
 if numberToMultiply == 1 :
 return 1
 else :
 return numberToMultiply * factorialFunction(numberToMultiply - 1)

 result = factorialFunction(3)
 print(result)
 //Outputs: 6

Das obige Programm gibt Ihnen das Ergebnis 6, das die Fakultät der Zahl 3 ist. Dies kann zunächst etwas verwirrend sein. Es wird helfen, wenn wir das Programm Schritt für Schritt durchlaufen.

  1. Wenn die Funktion aufgerufen wird, ist numberToMultiply gleich 3.
  2. Die Bedingung ist nicht erfüllt, also gehen wir in die else- Bedingung.
  3. Unsere Funktion gibt 3 * zurück, wird dann aber angehalten. Es muss sich selbst aufrufen, um den Rest des zurückgegebenen Werts zu bestimmen.
  4. Wenn die Funktion dieses Mal aufgerufen wird, ist der Wert von numberToMultiply gleich 2.
  5. Die Bedingung ist nicht erfüllt, also gehen wir in die else-Bedingung.
  6. Unsere Funktion gibt 2 * zurück, wird dann aber angehalten. Es muss sich selbst aufrufen, um den Rest des zurückgegebenen Werts zu bestimmen.
  7. Die Funktion wird noch einmal aufgerufen. Diesmal ist der Wert von numberToMultiply gleich 1.
  8. Unsere if- Bedingung ist erfüllt. Die Funktion gibt 1 zurück.
  9. Die Funktion aus Schritt 6 kann nun 2 * 1 zur Funktion in Schritt 3 zurückgeben.
  10. Die Funktion in Schritt drei kann jetzt 3 * 2 * 1 zurückgeben, was 6 ist.
Was ist Rekursion und wie verwenden Sie sie? - recursive algorithm

Rekursion ist ein kniffliges Konzept. Es kann hilfreich sein, sich vorzustellen, dass eine Funktion über einer anderen Funktion gestapelt wird. Sobald eine Funktion endgültig aufgelöst ist, kann sie die Informationen zurück in den Stapel senden, bis alle Funktionen ihre Antwort haben.

Dies ist eigentlich so ziemlich das, was Ihr Computer tut. Wenn Sie die Funktion aufrufen, wird sie gespeichert, bis sie zurückgegeben wird. Dies bedeutet, dass rekursive Funktionen viel mehr Speicher als eine Schleife benötigen.

Es ist also möglicherweise nicht effizient, Schleifen als rekursive Funktionen zu schreiben, aber es ist eine großartige Möglichkeit, ihre Konstruktion zu üben. Sie sollten in der Lage sein, Schleifen als rekursive Funktionen mit ähnlichen Ergebnissen zu codieren.

Ein Beispiel für die Konvertierung einer Schleife in eine rekursive Funktion

 print("Enter an even number:")
 i = int(input())
 while (i % 2) != 0 :
 print("That number is not even. Please enter a new number:")
 i = int(input())

Diese Schleife kann auch rekursiv geschrieben werden als:

 def recursiveFunction(number) :
 if (number % 2) == 0 :
 return number
 else:
 print("That number is not even. Please enter a new number:")
 recursiveFunction(int(input()))

 print("Enter and even number:")
 i = recursiveFunction(int(input()))

Der erste Schritt besteht darin, zu bestimmen, wann Ihre Funktion beendet werden soll. In diesem Fall möchten wir, dass es stoppt, sobald eine gerade Zahl eingegeben wird. In unserem Beispiel verfolgt die Nummer die Benutzereingabe. Wenn sie eine gerade Zahl eingeben, geben wir die Zahl zurück. Andernfalls werden wir weiterhin nach einer neuen Nummer fragen.

Um die Schleife einzurichten, rufen wir unsere Funktion erneut auf. Diesmal ist die Nummer, die wir an die nächste Funktion übergeben, die neue Nummer, die der Benutzer eingegeben hat. Der nächste Funktionsaufruf überprüft die Nummer.

Das ist eine wirklich schlechte Funktion! Ja, es wird geprüft, ob die Zahl gerade ist, wie in unserer Schleife, aber es ist nicht effizient. Jedes Mal, wenn der Benutzer eine ungerade Zahl eingibt, wird die Funktion gespeichert und eine neue Funktion aufgerufen. Wenn Sie dies genügend oft tun, wird Ihnen der Speicher ausgehen!

Verwandte: Grundlegende Python-Beispiele, mit denen Sie schnell lernen können

Ein reales Beispiel für eine rekursive Funktion

Die obigen Beispiele waren gute Beispiele dafür, wann keine Rekursion verwendet werden sollte. Wo wird die Rekursion verwendet? Ein gutes Beispiel dafür, wann Sie Rekursion verwenden möchten, ist die Suche in einem Binärbaum.

Was ist Rekursion und wie verwenden Sie sie? - 1024px Binary tree.svg

Wenn Daten in einem Binärbaum strukturiert sind, müssen Sie viele Pfade gehen, um nach Daten zu suchen. An jedem Punkt im Baum müssen Sie entscheiden, ob Sie rechts oder links weiter suchen möchten. Sie können speichern, welchen Teil des Baums Sie in einer Variablen besucht haben, aber eine rekursive Funktion kann diese Informationen natürlich verfolgen.

Stellen Sie sich vor, wir suchen die Nummer sechs im Baum oben. Wir könnten eine rekursive Funktion erstellen, die den Baum von links nach rechts durchsucht. Der Algorithmus würde ungefähr so ​​aussehen:

 FUNCTION searchTree(branchToSearch)
 IF find 6 OR end of tree THEN
 RETURN result
 ELSE
 PROCESS branch
 CALL FUNCTION searchTree(left)
 CALL FUNCTION searchTree(right)
 END FUNCTION

In diesem Pseudocode-Beispiel würde der Algorithmus zuerst die linke Seite des Baums durchsuchen. Bei jedem Besuch einer neuen Nummer wird die Funktion angehalten und gespeichert. Auf diese Weise können wir verfolgen, wo wir waren.

Der Algorithmus sucht immer die linke Seite so weit wie möglich zuerst. Sobald das Ende des Baums erreicht ist, wird der Suchbaum (links) abgeschlossen und die rechte Seite überprüft. Sobald beide Seiten überprüft wurden, sichert die Suche einen Zweig und überprüft weiterhin die rechte Seite.

Wenn die Algorithmen den gesamten Baum durchsuchen würden, würde dies in der folgenden Reihenfolge erfolgen:

2, 7, 2, 6, 5, 11, 5, 9 und 4

Überprüfen Sie, ob Sie den obigen Pseudocode verwenden können.

Überprüfung der Rekursion

Rekursion ist ein fortgeschrittenes Thema. Es wird einige Zeit dauern, um es zu verstehen und noch länger, um es gut zu codieren. Es ist hilfreich, wenn Sie Schritt für Schritt durch rekursive Funktionen gehen. Es kann sogar hilfreich sein, Karteikarten oder Haftnotizen zu stapeln, wenn Sie eine Funktion durchlaufen, wenn Sie lernen, jeden Funktionsaufruf darzustellen.

Wenn Sie eine rekursive Funktion schreiben, entscheiden Sie zunächst, wie Sie die Funktion beenden möchten. Bestimmen Sie als Nächstes, wie Sie Ihre Schleife einrichten. Identifizieren Sie, welche Informationen an den nächsten Funktionsaufruf gesendet und welche zurückgegeben werden müssen.

Der beste Weg, um Rekursion zu lernen, besteht darin, sie zu üben und aus Ihren Fehlern zu lernen. Schauen Sie sich einen Teil Ihres alten Codes an und fordern Sie sich heraus, Schleifen als rekursive Funktionen neu zu schreiben. Es wird Ihren Code wahrscheinlich nicht effizienter machen, aber es wird eine gute Praxis sein.