Verständnis der Rekursion mit JavaScript

Einige Probleme eignen sich besser für die Rekursion. Beispielsweise hat eine Sequenz wie eine Fibonacci -Sequenz eine rekursive Definition. Jede Zahl in der Sequenz ist die Summe der ersten beiden Zahlen in der Sequenz. Probleme, die mit Baumdatenstrukturen gebaut oder durchquert werden müssen, können ebenfalls durch Rekursion gelöst werden. Wenn Sie sich rekursiv denken, können Sie leistungsstarke Fähigkeiten vermitteln, um solche Probleme zu lösen.

In diesem Tutorial werde ich Schritt für Schritt erläutern, wie mehrere rekursive Funktionen funktionieren, und Ihnen einige Techniken zeigen, um rekursive Funktionen systematisch zu definieren.

Inhalt:

• Was ist Rekursion?
• Digitale Rekursion
• Listenrekursion
• Erstellen Sie eine Liste
• Schwanzrekursion
• Zusammenfassen

Was ist Rekursion?

Rekursiv definierte Funktionen sind Funktionen, die durch ihre vereinfachten Versionen selbst definiert sind. Hier ist ein vereinfachtes Beispiel:

 Funktion doa (n) {
    // ...
    if (n> 0) {
        DOA (N-1);
    }
}

Um konzeptionell zu verstehen, wie die Rekursion funktioniert, werden wir uns ein Beispiel ansehen, das codesunabhängig ist. Angenommen, Sie sind für die Beantwortung von Anrufen des Unternehmens verantwortlich. Da dies ein geschäftiges Unternehmen ist, Ihr Telefon verfügt über mehrere Telefonleitungen, können Sie gleichzeitig mehrere Telefonanrufe bearbeiten. Jede Telefonlinie hat eine Taste am Mobilteil, die beim Eintreffen auf dem Weg blinkt. Wenn Sie heute zur Arbeit gehen und das Telefon einschalten, blinken gleichzeitig vier Zeilen. Sie beantworten also alle Anrufe.

Sie nehmen die erste Zeile ab und sagen ihnen: "Bitte warten Sie." Als nächstes holen Sie die dritte Zeile ab und setzen sie in den Standby -Unternehmen und so weiter. Wenn Sie jeden Anruf beenden, kehren Sie zum vorherigen Anrufer zurück, vervollständigen Sie diesen Anruf und legen auf.

Jeder Aufruf in diesem Beispiel ähnelt einem rekursiven Aufruf in einer Funktion. Wenn Sie einen Anruf erhalten, wird er in den Anrufstapel (im Code) eingelegt. Wenn Sie einen Anruf nicht sofort ausfüllen können, setzen Sie ihn in Standby -Unternehmen. Wenn Ihr Funktionsaufruf nicht sofort berechnet werden kann, bleibt er im Anrufstapel. Wenn Sie den Anruf beantworten können, wird er abgeholt. Wenn Ihr Code Funktionsaufrufe berechnen kann, wird er aus dem Stapel herausgekommen. Denken Sie an diese Metapher, wenn Sie sich das folgende Code -Beispiel ansehen.

Digitale Rekursion

Alle rekursiven Funktionen erfordern einen Grundfall, damit sie beenden können. Wenn Sie jedoch nur einen Basisfall zu unserer Funktion hinzufügen, wird dies nicht unendlich verhindern. Die Funktion muss einen Schritt haben, um uns der Grundsituation näher zu bringen. Dies ist der rekursive Schritt. Im rekursiven Schritt wird das Problem auf eine kleinere Version des Problems reduziert.

Angenommen, Sie haben eine Funktion, die alle Zahlen ab n multipliziert. Dies wird als faktorielle Funktion bezeichnet, wir schreiben sie als 4!, Wenn n gleich 1 ist.

In jedem Schritt subtrahieren Sie 1 von der aktuellen Zahl. Was ist die rekursive Situation? Der rekursive Fall ist die Funktionstatsache (4).

16. Ist 4 gleich 1? NEIN. Fakten Sie (3).
17. Ist 3 gleich 1? NEIN. Setzen Sie Tatsache (2).
18. Ist 2 gleich 1? NEIN. Setzen Sie Fakt (1).
19. Ist 1 gleich 1? Ja. Gibt Fakt (2) zurück und gibt 2 zurück.
20. Holen Sie sich 3 * Tatsache (2) ist Fakt (4) und kehrt 24 zurück.

Hier ist eine andere Möglichkeit, um zu sehen, wie die Funktion jeden Anruf umgeht:

 <code>fact(4) 4 * fact(3) 4 * ( 3 * fact(2) ) 4 * ( 3 * ( 2 * fact(1) )) 4 * ( 3 * ( 2 * 1 ) ) 4 * ( 3 * 2 ) 4 * 6 24</code>

In rekursiven Fällen sollten sich die Parameter ändern und Sie dem Grundfall näher bringen. Dieser Parameter sollte in Basisfällen getestet werden. Im vorherigen Beispiel, da wir 1 im rekursiven Fall subtrahieren, testen wir im Grundfall, ob der Parameter gleich 0 ist.

Herausforderung

1. Implementieren Sie die Summenfunktion mit Schleifen anstelle von rekursiv.
2. Erstellen Sie eine Funktion, die sich rekursiv zwei Zahlen multipliziert. Zum Beispiel 0;
3. Vereinfacht die Filterfunktion so, dass alle Elemente aus der Liste entfernt werden. Zum Beispiel ["A", "B", "D"].

Schwanzrekursion

Die Schwanzrekursion ist eine Rekursionsform, mit der der Compiler die Tail -Call -Optimierung (TCO) durchführen kann, um viele Leistungsfehler der normalen Rekursion zu verhindern. Zusätzlich löst die Schwanzrekursion das Problem der maximalen Funktionsabwehrtiefe. Sie müssen die Funktion jedoch irgendwie schreiben, damit sie funktioniert.

Die Schwanzrekursion eignet sich für Funktionen, die rekursive Funktionen am Ende einer Funktion aufrufen. Hier ist beispielsweise die schwanzrekursive Version der Summe () -Funktion: Der gesamte Rückgabewert von sum () ist der gesamte Rückgabewert, sodass die Laufzeit die externe Funktion sicher verwerfen und nur die Ergebnisse der internen Funktion zurückgeben kann. Viele Menschen werden jedoch über so etwas stolpern:

 Funktion nottailrecursive (n) {
    // ...
    Return Nottailrecursive (N) 1
}

Sie denken vielleicht, dass dies die Schwanzrekursion verwendet, da die rekursive Funktion am Ende aufgerufen wird. Aber es tut es nicht. Dies liegt daran, dass JavaScript zu einer externen Funktion zurückkehren muss, um 1 hinzuzufügen.你可以重写它的方法之一是将1传递到参数中，这样内部函数就可以进行该计算。

Nicht alle Browser unterstützen derzeit die Tail -Call -Optimierung, aber sie befinden sich im ES -Standard, sodass wir in Zukunft möglicherweise mehr Unterstützung dafür sehen. Darüber hinaus ist es normalerweise eine gute Praxis, da es normalerweise Änderungen an Funktionsparametern isoliert.

Herausforderung

Rekonstruieren Sie in diesem Artikel eine rekursive Funktion in einer schwanzrekursiven Funktion.

Zusammenfassen

Es gibt drei Teile für rekursive Funktionen. Die erste ist die grundlegende Situation, die die Kündigungsbedingung ist. Der zweite ist der Schritt, der uns der Grundsituation näher bringt. Der dritte ist der rekursive Schritt, bei dem sich die Funktion mit vereinfachten Eingaben aufruft.

Rekursion ist wie Iteration. Jede Funktion, die Sie rekursiv oder eine Schleife verwenden können. Andere Dinge, die bei der Verwendung von Rekursion zu berücksichtigen sind, sind rekursive verschachtelte Listen und optimierte rekursive Anrufe.

Sie können die rekursive Funktion in eine rekursive Schwanzfunktion neu umsetzen, die Leistungsvorteile erzielen kann.

Eine gute Ressource, um die Rekursion weiter zu lernen, ist das Buch The Little Schemer. Es verwendet ein Q & A -Format, um Ihnen beizubringen, wie Sie rekursiv denken.

Dieser Beitrag wurde mit den Beiträgen von Jacob Jackson aktualisiert. Jacob ist ein Webentwickler, Tech -Autor, Freiberufler und Open -Source -Mitarbeiter.

Das obige ist der detaillierte Inhalt vonVerständnis der Rekursion mit JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!