Share
Einige Probleme werden natürlicherweise durch Rekursion gelöst. Beispielsweise hat eine Sequenz wie die Fibonacci-Sequenz eine rekursive Definition. Jede Nummer in der Sequenz ist die Summe der vorherigen zwei Nummern in der Sequenz. Probleme, bei denen Sie eine baumartige Datenstruktur erstellen oder durchqueren müssen, können auch durch Rekursion gelöst werden. Wenn Sie sich rekursiv denken, erhalten Sie eine mächtige Fähigkeit, solche Probleme anzugreifen.
In diesem Lernprogramm gehe ich Schritt für Schritt durch mehrere rekursive Funktionen, um zu sehen, wie sie funktionieren, und Sie zeigen Ihnen Techniken, mit denen Sie rekursive Funktionen systematisch definieren können.
Eine rekursiv definierte Funktion ist eine Funktion, die anhand einer einfacheren Version von sich selbst definiert wird. Dies ist ein vereinfachtes Beispiel:
Funktion doA (n) … doA (n-1);
Um zu verstehen, wie Rekursion konzeptionell funktioniert, betrachten wir ein Beispiel, das nichts mit Code zu tun hat. Stellen Sie sich vor, Sie sind dafür verantwortlich, Telefonanrufe bei der Arbeit zu beantworten. Da dies eine geschäftige Firma ist, verfügt Ihr Telefon über mehrere Telefonleitungen, sodass Sie mehrere Anrufe gleichzeitig abwickeln können. Jede Telefonleitung ist eine Taste am Empfänger, und wenn ein Anruf eingeht, blinkt die Taste. Heute, wenn Sie zur Arbeit kommen und das Telefon einschalten, blinken vier Leitungen gleichzeitig. So können Sie alle Anrufe beantworten.
Sie nehmen die erste Zeile und sagen ihnen "Bitte halten". Dann nehmen Sie die zweite Leitung und legen sie in die Warteschleife. Als nächstes nehmen Sie die dritte Zeile und legen sie in die Warteschleife. Zum Schluss beantworten Sie die vierte Leitung und sprechen mit dem Anrufer. Wenn Sie mit dem vierten Anrufer fertig sind, legen Sie auf und nehmen den dritten Anruf entgegen. Wenn Sie mit dem dritten Anruf fertig sind, legen Sie auf und nehmen den zweiten Anruf entgegen. Wenn Sie mit dem zweiten Anruf fertig sind, legen Sie auf und nehmen den ersten Anruf auf. Wenn Sie diesen Anruf beendet haben, können Sie das Telefon schließlich abstellen.
Jeder der Telefonanrufe in diesem Beispiel ist wie ein rekursiver Anruf in einer Funktion. Wenn Sie einen Anruf erhalten, wird er auf den Call Stack gelegt (im Code sprechen Sie). Wenn Sie einen Anruf nicht sofort abschließen können, halten Sie ihn an. Wenn Sie einen Funktionsaufruf haben, der nicht sofort ausgewertet werden kann, verbleibt er auf der Aufrufliste. Wenn Sie einen Anruf entgegennehmen können, wird er angenommen. Wenn Ihr Code einen Funktionsaufruf auswerten kann, wird er vom Stapel entfernt. Beachten Sie diese Analogie, wenn Sie die folgenden Codebeispiele durchgehen.
Alle rekursiven Funktionen benötigen einen Basisfall, damit sie beendet werden. Das Hinzufügen eines Basisfalls zu unserer Funktion verhindert jedoch nicht, dass es unendlich läuft. Die Funktion muss einen Schritt haben, um uns dem Basisfall näher zu bringen. Der letzte ist der rekursive Schritt. Im rekursiven Schritt wird das Problem auf eine kleinere Version des Problems reduziert.
Angenommen, Sie haben eine Funktion, die die Zahlen von 1 bis n summiert. Wenn zum Beispiel n = 4 ist, wird 1 + 2 + 3 + 4 addiert.
Zuerst bestimmen wir den Basisfall. Das Finden des Basisfalls kann auch als das Finden des Falls betrachtet werden, bei dem das Problem ohne Rekursion gelöst werden kann. In diesem Fall ist es, wenn n gleich Null ist. Null hat keine Teile, so dass unsere Rekursion bei 0 aufhören kann.
Bei jedem Schritt wird eine von der aktuellen Nummer abgezogen. Was ist der rekursive Fall? Der rekursive Fall ist die Funktionssumme, die mit der reduzierten Nummer aufgerufen wird.
Funktionssumme (num) if (num === 0) return 0; else return num + sum (- num) sum (4); // 10
Dies passiert bei jedem Schritt:
Auf diese Weise können Sie sehen, wie die Funktion jeden Aufruf verarbeitet:
Summe (4) 4 + Summe (3) 4 + (3 + Summe (2)) 4 + (3 + (2 + Summe (1))) 4 + (3 + (2 + (1 + Summe (0))) )) 4 + (3 + (2 + (1 + 0))) 4 + (3 + (2 + 1)) 4 + (3 + 3) 4 + 6 10
Das Argument sollte sich im rekursiven Fall ändern und Sie dem Basisfall näher bringen. Dieses Argument sollte im Basisfall getestet werden. Da wir im vorherigen Beispiel eins im rekursiven Fall subtrahieren, testen wir, ob das Argument in unserem Basisfall gleich Null ist.
Accentsconagua
multiplizieren (2,4) wird zurückkehren 8. Schreiben Sie für jeden Schritt, was passiert multiplizieren (2,4).Das Wiederholen einer Liste ähnelt dem Wiederholen einer Nummer, mit der Ausnahme, dass wir die Anzahl nicht bei jedem Schritt verringern, sondern die Liste bei jedem Schritt reduzieren, bis wir zu einer leeren Liste gelangen.
Betrachten Sie die Summenfunktion, die eine Liste als Eingabe verwendet und die Summe aller Elemente in der Liste zurückgibt. Dies ist eine Implementierung für die Funktionssumme:
Funktionssumme (l) if (leer (l)) return 0; else return car (l) + Summe (cdr (l));
Das leeren Funktion gibt true zurück, wenn die Liste keine Elemente enthält. Das Auto Funktion gibt das erste Element in der Liste zurück. Zum Beispiel, Auto ([1,2,3,4]) gibt 1 zurück cdr Funktion gibt die Liste ohne das erste Element zurück. Zum Beispiel, cdr ([1,2,3,4]) gibt [2,3,4] zurück. Was passiert, wenn wir ausführen? Summe ([1,2,3,4])?
Summe ([1,2,3,4]) 1 + Summe ([2,3,4]) 1 + (2 + Summe ([3,4])) 1 + (2 + (3 + Summe ([4 ]))) 1 + (2 + (3 + (4 + Summe ([])))) 1 + (2 + (3 + (4 + 0))) 1 + (2 + (3 + 4)) 1 + (2 + 7) 1 + 9 10
Überprüfen Sie bei einer Wiederholung in einer Liste, ob diese leer ist. Andernfalls führen Sie den rekursiven Schritt mit einer reduzierten Version der Liste durch.
Länge (['a', 'b', 'c', 'd']) sollte zurückkehren 4. Schreiben Sie, was bei jedem Schritt passiert.Im letzten Beispiel haben wir eine Nummer zurückgegeben. Angenommen, wir wollten eine Liste zurückgeben. Das würde bedeuten, dass wir, anstatt unserem rekursiven Schritt eine Zahl hinzuzufügen, eine Liste hinzufügen müssen. Betrachten Sie die Funktion Löschen, Das nimmt ein Element und eine Liste als Eingabe und gibt die Liste mit dem entfernten Element zurück. Nur der erste gefundene Artikel wird entfernt.
Funktion remove (item, l) if (leer (l)) return []; else if (eq (car (l), item)) return cdr (l); else return cons (Auto (l), entfernen (Artikel, cdr (l))); remove ('c', ['a', 'b', 'c', 'd']) // ['a', 'b', 'd']Hier die Gl Funktion gibt true zurück, wenn beide Eingänge gleich sind. Das Nachteile function nimmt ein Element und eine Liste als Eingaben und gibt eine neue Liste zurück, wobei das Element am Anfang hinzugefügt wird.
Wir prüfen, ob der erste Eintrag in der Liste dem zu entfernenden Eintrag entspricht. Ist dies der Fall, entfernen Sie das erste Element aus der Liste und geben Sie die neue Liste zurück. Wenn das erste Element nicht dem Element entspricht, das Sie entfernen möchten, nehmen wir das erste Element in der Liste und fügen es dem rekursiven Schritt hinzu. Der rekursive Schritt enthält die Liste, wobei das erste Element entfernt wurde.
Wir werden solange Elemente entfernen, bis wir zu unserem Basisfall gelangen, einer leeren Liste. Eine leere Liste bedeutet, dass wir alle Elemente in unserer Liste durchlaufen haben. Was macht entfernen ('c', ['a', 'b', 'c', 'd']) tun?
entfernen ('c', ['a', 'b', 'c', 'd']) cons ('a', entfernen ('c', ['b', 'c', 'd']) ) cons ('a', cons ('b', entfernen ('c', ['c', 'd']))) cons ('a', cons ('b', ['d']) cons ('a', ['b', 'd']) ['a', 'b', 'd']In einer Situation, in der wir eine Liste erstellen müssen, nehmen wir das erste Element und fügen es dem rekursiven Teil unserer Liste hinzu.
entfernen ('c', ['a', 'b', 'c', 'd', 'c']) gibt ['a', 'b', 'd'] zurück. Schreiben Sie Schritt für Schritt, was passiert.Eine rekursive Funktion besteht aus drei Teilen. Der erste ist der Basisfall, der die Beendigungsbedingung darstellt. Der zweite Schritt ist der Schritt, um uns unserem Basisfall näher zu bringen. Der dritte ist der rekursive Schritt, bei dem sich die Funktion mit der reduzierten Eingabe aufruft.
Rekursion ist wie eine Iteration. Jede Funktion, die Sie rekursiv definieren können, kann auch über Schleifen definiert werden. Weitere Aspekte, die bei der Verwendung der Rekursion zu berücksichtigen sind, finden sich in verschachtelten Listen und die Optimierung rekursiver Aufrufe.
Eine großartige Quelle, um weiter über Rekursion zu lernen, ist das Buch Der kleine Schemer. Es zeigt Ihnen, wie Sie mit einem Frage- und Antwortformat rekursiv denken.
