Wie Rekursion funktioniert - Erklärt mit Flussdiagrammen und einem Video

"Um die Rekursion zu verstehen, muss man zuerst die Rekursion verstehen."

Rekursion kann schwer zu verstehen sein - insbesondere für neue Programmierer. In seiner einfachsten Form ist eine rekursive Funktion eine, die sich selbst aufruft. Lassen Sie mich versuchen, dies anhand eines Beispiels zu erklären.

Stellen Sie sich vor, Sie öffnen Ihre Schlafzimmertür und sie ist verschlossen. Ihr dreijähriger Sohn kommt um die Ecke und lässt Sie wissen, dass er den einzigen Schlüssel in einer Schachtel versteckt hat. („Genau wie er“, denken Sie.) Sie kommen zu spät zur Arbeit und müssen wirklich in den Raum, um Ihr Hemd zu bekommen.

Sie öffnen die Box nur, um… weitere Boxen zu finden. Boxen innerhalb von Boxen. Und Sie wissen nicht, welcher den Schlüssel hat! Sie müssen das Shirt bald bekommen, also müssen Sie sich einen guten Algorithmus überlegen, um diesen Schlüssel zu finden.

Es gibt zwei Hauptansätze, um einen Algorithmus für dieses Problem zu erstellen: iterativ und rekursiv. Hier sind beide Ansätze als Flussdiagramme:

Welcher Ansatz erscheint Ihnen einfacher?

Der erste Ansatz verwendet eine while-Schleife. Während der Stapel nicht leer ist, schnappen Sie sich eine Kiste und schauen Sie durch. Hier ist ein von JavaScript inspirierter Pseudocode, der zeigt, was passiert. (Pseudocode ist wie Code geschrieben, soll aber eher menschlicher Sprache ähneln.)

function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } }}

Der zweite Weg verwendet die Rekursion. Denken Sie daran, bei der Rekursion ruft sich eine Funktion selbst auf. Hier ist der zweite Weg im Pseudocode.

function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }

Beide Ansätze erreichen dasselbe. Der Hauptzweck der Verwendung des rekursiven Ansatzes besteht darin, dass das Lesen klarer ist, sobald Sie ihn verstanden haben. Die Verwendung der Rekursion bietet keinen Leistungsvorteil. Der iterative Ansatz mit Schleifen kann manchmal schneller sein. Vor allem aber wird manchmal die Einfachheit der Rekursion bevorzugt.

Da viele Algorithmen Rekursion verwenden, ist es wichtig zu verstehen, wie es funktioniert. Wenn Ihnen die Rekursion immer noch nicht einfach erscheint, machen Sie sich keine Sorgen: Ich werde noch ein paar Beispiele durchgehen.

Basisfall und rekursiver Fall

Beim Schreiben einer rekursiven Funktion müssen Sie auf eine Endlosschleife achten. In diesem Fall ruft sich die Funktion immer wieder selbst auf… und hört nie auf, sich selbst aufzurufen!

Beispielsweise möchten Sie möglicherweise eine Countdown-Funktion schreiben. Sie können es rekursiv in JavaScript wie folgt schreiben:

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1)} countdown(5); // This is the initial call to the function.

Diese Funktion zählt für immer herunter. Wenn Sie versehentlich Code mit einer Endlosschleife ausführen, können Sie "Strg-C" drücken, um Ihr Skript zu beenden. (Wenn Sie manchmal CodePen wie mich verwenden, müssen Sie am Ende der URL "? Turn_off_js = true" hinzufügen.)

Eine rekursive Funktion muss immer sagen, wann sie aufhören soll, sich zu wiederholen. Eine rekursive Funktion sollte immer aus zwei Teilen bestehen: dem rekursiven Fall und dem Basisfall. Der rekursive Fall ist, wenn sich die Funktion selbst aufruft. Der Basisfall ist, wenn die Funktion aufhört, sich selbst aufzurufen. Dies verhindert Endlosschleifen.

Hier ist wieder die Countdown-Funktion mit einem Basisfall:

function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1); } } countdown(5); // This is the initial call to the function.

Es ist möglicherweise nicht genau ersichtlich, was in dieser Funktion geschieht. Ich werde durchgehen, was passiert, wenn Sie die Countdown-Funktion aufrufen und "5" übergeben.

Wir beginnen mit dem Ausdrucken der Nummer 5 mit console.log. Da fünf nicht kleiner oder gleich Null ist, gehen wir zur else-Anweisung. Dort rufen wir die Countdown-Funktion erneut mit der Nummer vier auf (5–1 = 4?).

Wir protokollieren die Zahl 4. Auch hier iist sie nicht kleiner oder gleich Null, also gehen wir zur else-Anweisung und rufen den Countdown mit 3 auf. Dies wird bis fortgesetztigleich Null. Wenn das passiert, melden wir die Zahl Null und dann iist kleiner als oder gleich Null ist . Wir kommen schließlich zur return-Anweisung und verlassen die Funktion.

Der Call Stack

Rekursive Funktionen verwenden den sogenannten "Aufrufstapel". Wenn ein Programm eine Funktion aufruft, wird diese Funktion über dem Aufrufstapel angezeigt. Dies ähnelt einem Stapel Bücher. Sie fügen Dinge einzeln hinzu. Wenn Sie dann bereit sind, etwas auszuziehen, nehmen Sie immer den obersten Gegenstand ab.

Ich werde Ihnen den Aufrufstapel in Aktion mit der factorialFunktion zeigen. factorial(5)wird als 5 geschrieben! und es ist so definiert: 5! = 5 * 4 * 3 * 2 * 1. Hier ist eine rekursive Funktion zur Berechnung der Fakultät einer Zahl:

function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }

Nun wollen wir sehen, was passiert, wenn Sie aufrufen. fact(3)Die folgende Abbildung zeigt, wie sich der Stapel Zeile für Zeile ändert. Das oberste Feld im Stapel zeigt an, welchen Anruf factSie gerade tätigen.

Beachten Sie, wie jeder Anruf facteine eigene Kopie von hat x. Dies ist sehr wichtig, damit die Rekursion funktioniert. Sie können nicht auf die Kopie einer anderen Funktion zugreifen x.

Hast du den Schlüssel schon gefunden?

Kehren wir kurz zum ursprünglichen Beispiel zurück, in dem in verschachtelten Feldern nach einem Schlüssel gesucht wird. Denken Sie daran, dass die erste Methode iterativ mit Schleifen durchgeführt wurde. Mit dieser Methode erstellen Sie einen Stapel von Kisten zum Durchsuchen, sodass Sie immer wissen, welche Kisten Sie noch durchsuchen müssen.

Der rekursive Ansatz enthält jedoch keinen Stapel. Woher weiß Ihr Algorithmus, welche Boxen Sie noch suchen müssen? Der „Stapel Kisten“ wird auf dem Stapel gespeichert. Dies ist ein Stapel von halbfertigen Funktionsaufrufen, von denen jeder eine eigene halbfertige Liste von Feldern hat, die durchgesehen werden müssen. Der Stapel verfolgt den Stapel Kisten für Sie!

Und dank der Rekursion können Sie endlich den Schlüssel finden und Ihr Hemd bekommen!

Sie können sich auch dieses 5-minütige Video ansehen, das ich über Rekursion gemacht habe. Es sollte diese Rekursionskonzepte verstärken.

Fazit

Ich hoffe, dieser Artikel hat Ihnen mehr Klarheit über die Rekursion in der Programmierung gebracht. Dieser Artikel basiert auf einer Lektion in meinem neuen Videokurs von Manning Publications mit dem Titel Algorithms in Motion. Der Kurs (und auch dieser Artikel) basiert auf dem erstaunlichen Buch Grokking Algorithms von Adit Bhargava. Er ist derjenige, der alle lustigen Illustrationen in diesem Artikel gezeichnet hat.

Wenn Sie am besten durch Bücher lernen, holen Sie sich das Buch! Wenn Sie am besten durch Videos lernen, sollten Sie meinen Kurs kaufen.

Mit dem Code ' 39carnes ' erhalten Sie 39% Rabatt auf meinen Kurs !

Und um die Rekursion wirklich zu verstehen, müssen Sie diesen Artikel erneut lesen. ?