pow(2, 2) = 4pow(2, 3) = 8pow(2, 4) = 16

 if n==1 = x /pow(x, n) = \ else = x * pow(x, n - 1)

Die Variablen sind gleich, aber die Zeile ändert sich, der Kontext ist jetzt also:

• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Umx * pow(x, n - 1)zu berechnen, müssen wir einen subcall vonpowmit neuen Argumentenpow(2, 2).,

pow (2, 2)

Um einen verschachtelten Aufruf durchzuführen, merkt sich JavaScript den aktuellen Ausführungskontext im Ausführungskontextstapel.

Hier nennen wir die gleiche Funktion pow, aber es spielt absolut keine Rolle. Der Prozess ist für alle Funktionen gleich:

1. Der aktuelle Kontext wird oben auf dem Stapel „gespeichert“.
2. Der neue Kontext wird für den Subcall erstellt.
3. Wenn der Subcall beendet ist, wird der vorherige Kontext aus dem Stapel entfernt und seine Ausführung wird fortgesetzt.,

Hier ist der Kontextstapel, als wir den Subcall pow(2, 2):

• Context: { x: 2, n: 2, in Zeile 1 } pow(2, 2)
• Context: { x: 2, n: 3, in Zeile 5 } pow(2, 3)

Der neue aktuelle Ausführungskontext ist oben (und fett), und frühere erinnerte Kontexte sind unten.

Wenn wir den Subcall beenden, ist es einfach, den vorherigen Kontext fortzusetzen, da sowohl Variablen als auch der genaue Ort des Codes dort gespeichert bleiben, wo er angehalten hat.,

pow (2, 1)

Der Vorgang wiederholt sich: In Zeile 5 wird ein neuer subcall erstellt, jetzt mit den Argumenten x=2, n=1.,

Es wird ein neuer Ausführungskontext erstellt, der vorherige wird über den Stapel geschoben:

• Kontext: { x: 2, n: 1, in Zeile 1 } pow(2, 1)
• Kontext: { x: 2, n: 2, in Zeile 5 } pow(2, 2)
• Kontext: { x: 2, n: 3, in Zeile 5 } pow(2, 3)

Es gibt jetzt 2 alte Kontexte und 1 läuft derzeit für pow(2, 1).,

Der Ausgang

Während der Ausführung von pow(2, 1) ist anders als zuvor die Bedingung n == 1 wahrheitsgemäß, so dass der erste Zweig von if funktioniert:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}

Es gibt keine verschachtelten Aufrufe mehr, daher wird die Funktion beendet und 2.

Wenn die Funktion beendet ist, wird ihr Ausführungskontext nicht mehr benötigt, sodass er aus dem Speicher entfernt wird., Der vorherige wird oben auf dem Stapel wiederhergestellt:

• Kontext: { x: 2, n: 2, in Zeile 5 } pow(2, 2)
• Kontext: { x: 2, n: 3, in Zeile 5 } pow(2, 3)

Dann wird der vorherige Kontext wiederhergestellt:

• Kontext: { x: 2, n: 3, in Zeile 5 } pow(2, 3)

Wenn es beendet ist, haben wir ein Ergebnis von pow(2, 3) = 8.

Die Rekursionstiefe betrug in diesem Fall: 3.

Wie aus den obigen Abbildungen ersichtlich, entspricht die Rekursionstiefe der maximalen Anzahl von Kontexten im Stapel.

Beachten Sie die Speicheranforderungen. Kontexte nehmen Erinnerung., In unserem Fall erfordert das Erhöhen auf die Potenz von n tatsächlich den Speicher für n – Kontexte für alle niedrigeren Werte von n.

Ein schleifenbasierter Algorithmus ist speichersparender:

function pow(x, n) { let result = 1; for (let i = 0; i < n; i++) { result *= x; } return result;}

Die iterative pow verwendet dabei einen einzigen Kontext, der i und result ändert. Der Speicherbedarf ist gering, fest und hängt nicht von nab.,

Jede Rekursion kann als Schleife neu geschrieben werden. Die Schleifenvariante kann in der Regel effektiver gemacht werden.

…Aber manchmal ist das Umschreiben nicht trivial, insbesondere wenn die Funktion abhängig von den Bedingungen verschiedene rekursive Subcalls verwendet und ihre Ergebnisse zusammenführt oder wenn die Verzweigung komplizierter ist. Und die Optimierung kann unnötig sein und die Bemühungen völlig nicht wert sein.

Rekursion kann einen kürzeren Code geben, einfacher zu verstehen und zu unterstützen. Optimierungen sind nicht an jedem Ort erforderlich, meistens brauchen wir einen guten Code, deshalb wird er verwendet.,

Rekursive traversals

Eine weitere großartige Anwendung der Rekursion ist eine rekursive Traversal.

Stellen Sie sich vor, wir haben eine Firma. Die Personalstruktur kann als Objekt dargestellt werden:

Mit anderen Worten, ein Unternehmen hat Abteilungen.

• Eine Abteilung kann eine Reihe von Mitarbeitern haben. Zum Beispiel sales Abteilung hat 2 Mitarbeiter: John und Alice.

• Oder eine Abteilung kann in Unterabteilungen aufgeteilt werden, wie development hat zwei Zweige: sites und internals. Jeder von ihnen hat sein eigenes Personal.,

• Es ist auch möglich, dass eine Unterabteilung, wenn sie wächst, in Unterabteilungen (oder Teams) unterteilt wird.

  Zum Beispiel kann die Abteilung sites in Zukunft in Teams für siteA und siteBaufgeteilt werden. Und sie können möglicherweise noch mehr spalten. Das ist nicht auf dem Bild, nur etwas im Sinn zu haben.

Angenommen, wir möchten, dass eine Funktion die Summe aller Gehälter erhält. Wie können wir das tun?

Ein iterativer Ansatz ist nicht einfach, da die Struktur nicht einfach ist., Die erste Idee könnte sein, eine for Schleife über company mit verschachtelten Subloop über Abteilungen der 1.Ebene zu erstellen. Aber dann brauchen wir mehr verschachtelte Subloops, um über die Mitarbeiter in Abteilungen der 2. Ebene zu iterieren, wie sites… Und dann eine weitere Subloop in denen für Abteilungen der 3. Ebene, die in der Zukunft erscheinen könnten? Wenn wir 3-4 verschachtelte Subloops in den Code einfügen, um ein einzelnes Objekt zu durchlaufen, wird es ziemlich hässlich.

Versuchen wir es mit Rekursion.,

Wie wir sehen können, gibt es zwei mögliche Fälle, wenn unsere Funktion eine Abteilung zur Summe bringt:

1. Entweder es ist eine „einfache“ Abteilung mit einer Reihe von Personen – dann können wir die Gehälter in einer einfachen Schleife summieren.
2. Oder es ist ein Objekt mit Unterabteilungen – dann können wir rekursive Aufrufe ausführen, um die Summe für jeden der Unterabschnitte abzurufen und die Ergebnisse zu kombinieren.

Der erste Fall ist die Basis der Rekursion, der triviale Fall, wenn wir ein Array erhalten.

Der zweite Fall, wenn wir ein Objekt erhalten, ist der rekursive Schritt., Eine komplexe Aufgabe ist in Unteraufgaben für kleinere Abteilungen aufgeteilt. Sie können sich wiederum wieder teilen, aber früher oder später endet die Teilung bei (1).

Der Algorithmus ist wahrscheinlich noch einfacher aus dem Code zu lesen:

Der Code ist kurz und leicht zu verstehen (hoffentlich?). Das ist die Kraft der Rekursion. Es funktioniert auch für jede Ebene der Subdepartment-Verschachtelung.,

Hier ist das Diagramm der Aufrufe:

Beachten Sie, dass der Code intelligente Funktionen verwendet, die wir abgedeckt haben vorher:

• Methode arr.reduce im Kapitel Array Methoden erklärt, um die Summe des Arrays zu erhalten.
• Schleife for(val of Object.values(obj)) um Objektwerte zu iterieren: Object.values gibt ein Array davon zurück.,

Rekursive Strukturen

Eine rekursive (rekursiv definierte) Datenstruktur ist eine Struktur, die sich in Teilen repliziert.

Wir haben es gerade im Beispiel einer Unternehmensstruktur oben gesehen.

Eine Unternehmensabteilung ist:

• Entweder eine Reihe von Personen.
• Oder ein Objekt mit Abteilungen.

Für Webentwickler gibt es viel bekanntere Beispiele: HTML-und XML-Dokumente.

Im HTML-Dokument kann ein HTML-Tag eine Liste von:

• Textstücken enthalten.
• HTML-Kommentare.,
• Andere HTML-Tags (die wiederum Textteile/Kommentare oder andere Tags usw. enthalten können).

Das ist wieder einmal eine rekursive Definition.

Zum besseren Verständnis werden wir eine weitere rekursive Struktur namens „Verknüpfte Liste“ behandeln, die in einigen Fällen eine bessere Alternative für Arrays sein könnte.

Verknüpfte Liste

Stellen Sie sich vor, wir möchten eine geordnete Liste von Objekten speichern.

Die Natürliche Wahl wäre ein array:

let arr = ;

…Aber es gibt ein problem mit arrays., Die Operationen“ Element löschen „und“ Element einfügen “ sind teuer. Zum Beispiel muss arr.unshift(obj) Operation alle Elemente neu nummerieren, um Platz für eine neue obj, und wenn das Array groß ist, braucht es Zeit. Gleiches gilt für arr.shift().

Die einzigen strukturellen Änderungen, die keine Massenumnummerierung erfordern, sind diejenigen, die mit dem Ende des Arrays arbeiten: arr.push/pop. Ein Array kann also für große Warteschlangen ziemlich langsam sein, wenn wir mit dem Anfang arbeiten müssen.,

Wenn wir wirklich schnelles Einfügen/Löschen benötigen, können wir alternativ eine andere Datenstruktur auswählen, die als verknüpfte Liste bezeichnet wird.

Das verknüpfte Listenelement wird rekursiv als Objekt definiert mit:

• value.
• next Eigenschaft, die auf das nächste verknüpfte Listenelement verweist, oder null wenn dies das Ende ist.,

For instance:

let list = { value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: null } } }};

Graphical representation of the list:

An alternative code for creation:

let list = { value: 1 };list.next = { value: 2 };list.next.next = { value: 3 };list.next.next.next = { value: 4 };list.next.next.next.next = null;

Here we can even more clearly see that there are multiple objects, each one has the value and next pointing to the neighbour., Die Variable list ist das erste Objekt in der Kette, daher können wir nach next – Zeigern jedes Element erreichen.

Die Liste lässt sich einfach in mehrere Teile aufteilen und später wieder zusammenfügen:

let secondList = list.next.next;list.next.next = null;

Beitreten:

list.next.next = secondList;

Und sicherlich können wir Elemente an jedem Ort einfügen oder entfernen.,head of the list:

To remove a value from the middle, change next of the previous one:

list.next = list.next.next;

We made list.next jump over 1 to value 2., Der Wert 1 ist nun von der Kette ausgeschlossen. Wenn es nirgendwo anders gespeichert ist, wird es automatisch aus dem Speicher entfernt.

Im Gegensatz zu Arrays gibt es keine Massenumnummerierung, wir können Elemente leicht neu anordnen.

Listen sind natürlich nicht immer besser als Arrays. Sonst würde jeder nur Listen verwenden.

Der Hauptnachteil besteht darin, dass wir anhand seiner Nummer nicht einfach auf ein Element zugreifen können. In einem Array ist das einfach: ist eine direkte Referenz., Aber in der Liste müssen wir vom ersten Element ausgehen und next mal, um das N-te Element zu erhalten.

…Aber wir brauchen solche Operationen nicht immer. Zum Beispiel, wenn wir eine Warteschlange oder sogar eine Deque benötigen-die geordnete Struktur, die sehr schnelles Hinzufügen/Entfernen von Elementen von beiden Enden ermöglichen muss, aber der Zugriff auf die Mitte ist nicht erforderlich.

Listen können erweitert werden:

• Wir können die Eigenschaft prev zusätzlich zu next hinzufügen, um auf das vorherige Element zu verweisen und einfach zurückzukehren.,
• Wir können auch eine Variable mit dem Namen tail hinzufügen, die auf das letzte Element der Liste verweist (und diese beim Hinzufügen/Entfernen von Elementen vom Ende aktualisiert).
• …Die Datenstruktur kann je nach Bedarf variieren.

Zusammenfassung

Begriffe:

• Rekursion ist ein Programmierbegriff, der das Aufrufen einer Funktion von sich aus bedeutet. Rekursive Funktionen können verwendet werden, um Aufgaben auf elegante Weise zu lösen.

  Wenn sich eine Funktion selbst aufruft, wird dies als Rekursionsschritt bezeichnet., Die Basis der Rekursion sind Funktionsargumente, die die Aufgabe so einfach machen, dass die Funktion keine weiteren Aufrufe ausführt.

• Eine rekursiv definierte Datenstruktur ist eine Datenstruktur, die mit sich selbst definiert werden kann.

  Die verknüpfte Liste kann beispielsweise als Datenstruktur definiert werden, die aus einem Objekt besteht, das auf eine Liste (oder null) verweist.

  list = { value, next -> list }

  Bäume wie der HTML-Elementbaum oder der Abteilungsbaum aus diesem Kapitel sind ebenfalls natürlich rekursiv: Sie verzweigen sich und jeder Zweig kann andere Zweige haben.,

  Rekursive Funktionen können verwendet werden, um sie zu gehen, wie wir im Beispiel sumSalary gesehen haben.

Jede rekursive Funktion kann in eine iterative umgeschrieben werden. Und das ist manchmal erforderlich, um Sachen zu optimieren. Für viele Aufgaben ist eine rekursive Lösung jedoch schnell genug und einfacher zu schreiben und zu unterstützen.