Kehren wir zu den Funktionen zurück und untersuchen sie genauer.
Unser erstes Thema wird Rekursion sein.
Wenn Ihnen das Programmieren nicht neu ist, ist es wahrscheinlich vertraut und Sie können dieses Kapitel überspringen.
Rekursion ist ein Programmiermuster, das in Situationen nützlich ist, in denen eine Aufgabe auf natürliche Weise in mehrere Aufgaben derselben Art, jedoch einfacher, aufgeteilt werden kann. Oder wenn eine Aufgabe in eine einfache Aktion und eine einfachere Variante derselben Aufgabe vereinfacht werden kann. Oder, wie wir gleich sehen werden, mit bestimmten Datenstrukturen umzugehen.
Wenn eine Funktion eine Aufgabe löst, kann sie dabei viele andere Funktionen aufrufen. Ein Teilfall hierfür ist, wenn eine Funktion sich selbst aufruft. Das nennt man Rekursion .
Um mit etwas Einfachem zu beginnen: Schreiben wir eine Funktion pow(x, n) , die x auf eine natürliche Potenz von n erhöht. Mit anderen Worten, multipliziert x n -mal mit sich selbst.
pow(2, 2) = 4 pow(2, 3) = 8 pow(2, 4) = 16
Es gibt zwei Möglichkeiten, es umzusetzen.
Iteratives Denken: die for Schleife:
Funktion pow(x, n) {
sei Ergebnis = 1;
// Ergebnis n-mal in der Schleife mit x multiplizieren
for (sei i = 0; i < n; i++) {
Ergebnis *= x;
}
Ergebnis zurückgeben;
}
alarm( pow(2, 3) ); // 8Rekursives Denken: Vereinfachen Sie die Aufgabe und nennen Sie sich selbst:
Funktion pow(x, n) {
if (n == 1) {
x zurückgeben;
} anders {
return x * pow(x, n - 1);
}
}
alarm( pow(2, 3) ); // 8Bitte beachten Sie, dass sich die rekursive Variante grundlegend unterscheidet.
Wenn pow(x, n) aufgerufen wird, teilt sich die Ausführung in zwei Zweige:
wenn n==1 = x
/
pow(x, n) =
else = x * pow(x, n - 1) Wenn n == 1 , dann ist alles trivial. Sie wird Rekursionsbasis genannt, weil sie sofort das offensichtliche Ergebnis liefert: pow(x, 1) gleich x .
Ansonsten können wir pow(x, n) als x * pow(x, n - 1) darstellen. In der Mathematik würde man x n = x * x n-1 schreiben. Dies wird als rekursiver Schritt bezeichnet: Wir wandeln die Aufgabe in eine einfachere Aktion (Multiplikation mit x ) und einen einfacheren Aufruf derselben Aufgabe ( pow mit niedrigerem n ) um. Die nächsten Schritte vereinfachen es immer weiter, bis n 1 erreicht.
Wir können auch sagen, dass pow sich selbst rekursiv aufruft, bis n == 1 .
Um beispielsweise pow(2, 4) zu berechnen, führt die rekursive Variante die folgenden Schritte aus:
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
Die Rekursion reduziert also einen Funktionsaufruf auf einen einfacheren und dann auf einen noch einfacheren und so weiter, bis das Ergebnis offensichtlich wird.
Die Rekursion ist normalerweise kürzer
Eine rekursive Lösung ist normalerweise kürzer als eine iterative.
Hier können wir dasselbe mit dem Bedingungsoperator umschreiben ? anstelle von if um pow(x, n) prägnanter und dennoch gut lesbar zu machen:
Funktion pow(x, n) {
return (n == 1)? x : (x * pow(x, n - 1));
} Die maximale Anzahl verschachtelter Aufrufe (einschließlich des ersten) wird als Rekursionstiefe bezeichnet. In unserem Fall wird es genau n sein.
Die maximale Rekursionstiefe wird durch die JavaScript-Engine begrenzt. Wir können uns darauf verlassen, dass es 10.000 ist, einige Motoren erlauben mehr, aber 100.000 ist für die meisten wahrscheinlich außerhalb des Grenzwerts. Es gibt automatische Optimierungen, die Abhilfe schaffen („Tail Calls Optimizations“), diese werden jedoch noch nicht überall unterstützt und funktionieren nur in einfachen Fällen.
Das schränkt die Anwendung der Rekursion ein, bleibt aber dennoch sehr weitreichend. Es gibt viele Aufgaben, bei denen die rekursive Denkweise zu einem einfacheren Code führt, der leichter zu warten ist.
Sehen wir uns nun an, wie rekursive Aufrufe funktionieren. Dazu schauen wir unter die Haube der Funktionen.
Die Informationen über den Ausführungsprozess einer laufenden Funktion werden in ihrem Ausführungskontext gespeichert.
Der Ausführungskontext ist eine interne Datenstruktur, die Details zur Ausführung einer Funktion enthält: wo sich der Kontrollfluss jetzt befindet, die aktuellen Variablen, this Wert (wir verwenden ihn hier nicht) und einige andere interne Details.
Einem Funktionsaufruf ist genau ein Ausführungskontext zugeordnet.
Wenn eine Funktion einen verschachtelten Aufruf durchführt, geschieht Folgendes:
Die aktuelle Funktion wird angehalten.
Der damit verbundene Ausführungskontext wird in einer speziellen Datenstruktur gespeichert, die als Ausführungskontextstapel bezeichnet wird.
Der verschachtelte Aufruf wird ausgeführt.
Nach Beendigung wird der alte Ausführungskontext vom Stapel abgerufen und die äußere Funktion wird an der Stelle fortgesetzt, an der sie gestoppt wurde.
Mal sehen, was während des pow(2, 3) -Aufrufs passiert.
Zu Beginn des Aufrufs pow(2, 3) speichert der Ausführungskontext folgende Variablen: x = 2, n = 3 , der Ausführungsfluss befindet sich in Zeile 1 der Funktion.
Wir können es skizzieren als:
Kontext: { x: 2, n: 3, in Zeile 1 } pow(2, 3)
Dann beginnt die Ausführung der Funktion. Die Bedingung n == 1 ist falsch, daher geht der Fluss weiter zum zweiten Zweig von if :
Funktion pow(x, n) {
if (n == 1) {
x zurückgeben;
} anders {
return x * pow(x, n - 1);
}
}
alarm( pow(2, 3) );Die Variablen sind dieselben, aber die Zeile ändert sich, sodass der Kontext jetzt lautet:
Kontext: { x: 2, n: 3, in Zeile 5 } pow(2, 3)
Um x * pow(x, n - 1) zu berechnen, müssen wir einen Unteraufruf von pow mit den neuen Argumenten pow(2, 2) durchführen.
Um einen verschachtelten Aufruf durchzuführen, merkt sich JavaScript den aktuellen Ausführungskontext im Ausführungskontextstapel .
Hier nennen wir dieselbe Funktion pow , aber das spielt absolut keine Rolle. Der Ablauf ist für alle Funktionen gleich:
Der aktuelle Kontext wird oben im Stapel „gespeichert“.
Der neue Kontext wird für den Unteraufruf erstellt.
Wenn der Unteraufruf beendet ist, wird der vorherige Kontext vom Stapel entfernt und seine Ausführung fortgesetzt.
Hier ist der Kontextstapel, als wir den Unteraufruf pow(2, 2) eingegeben haben:
Kontext: { x: 2, n: 2, in Zeile 1 } pow(2, 2)
Kontext: { x: 2, n: 3, in Zeile 5 } pow(2, 3)
Der neue aktuelle Ausführungskontext ist oben (und fett) und zuvor gespeicherte Kontexte unten.
Wenn wir den Unteraufruf beendet haben, ist es einfach, den vorherigen Kontext fortzusetzen, da beide Variablen und die genaue Stelle des Codes, an der er aufgehört hat, erhalten bleiben.
Bitte beachten Sie:
Hier im Bild verwenden wir das Wort „Zeile“, da es in unserem Beispiel nur einen Unteraufruf in der Zeile gibt, aber im Allgemeinen kann eine einzelne Codezeile mehrere Unteraufrufe enthalten, wie z. B. pow(…) + pow(…) + somethingElse(…) .
Präziser wäre es also zu sagen, dass die Ausführung „unmittelbar nach dem Unteraufruf“ wieder aufgenommen wird.
Der Vorgang wiederholt sich: In Zeile 5 wird ein neuer Unteraufruf durchgeführt, jetzt mit den Argumenten x=2 , n=1 .
Ein neuer Ausführungskontext wird erstellt, der vorherige wird oben auf den Stapel verschoben:
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 zwei alte Kontexte und einer, der derzeit für pow(2, 1) ausgeführt wird.
Während der Ausführung von pow(2, 1) ist im Gegensatz zu zuvor die Bedingung n == 1 wahr, sodass der erste Zweig von if funktioniert:
Funktion pow(x, n) {
if (n == 1) {
x zurückgeben;
} anders {
return x * pow(x, n - 1);
}
} Es gibt keine weiteren verschachtelten Aufrufe, daher wird die Funktion beendet und gibt 2 zurück.
Wenn die Funktion beendet ist, wird ihr Ausführungskontext nicht mehr benötigt und daher aus dem Speicher entfernt. 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)
Die Ausführung von pow(2, 2) wird fortgesetzt. Es verfügt über das Ergebnis des Unteraufrufs pow(2, 1) und kann daher auch die Auswertung von x * pow(x, n - 1) abschließen und 4 zurückgeben.
Dann wird der vorherige Kontext wiederhergestellt:
Kontext: { x: 2, n: 3, in Zeile 5 } pow(2, 3)
Wenn es fertig ist, haben wir ein Ergebnis von pow(2, 3) = 8 .
Die Rekursionstiefe betrug in diesem Fall: 3 .
Wie wir aus den Abbildungen oben sehen können, entspricht die Rekursionstiefe der maximalen Anzahl von Kontexten im Stapel.
Beachten Sie den Speicherbedarf. Kontexte brauchen Erinnerung. In unserem Fall erfordert die Potenzierung von n tatsächlich den Speicher für n Kontexte, für alle niedrigeren Werte von n .
Ein schleifenbasierter Algorithmus ist speichersparender:
Funktion pow(x, n) {
sei Ergebnis = 1;
for (sei i = 0; i < n; i++) {
Ergebnis *= x;
}
Ergebnis zurückgeben;
} Das iterative pow verwendet einen einzelnen Kontext, i und result im Prozess ändert. Sein Speicherbedarf ist gering, fest und hängt nicht von n ab.
Jede Rekursion kann als Schleife umgeschrieben werden. Die Schleifenvariante kann in der Regel effektiver gestaltet werden.
… Aber manchmal ist das Umschreiben nicht trivial, insbesondere wenn eine Funktion je nach Bedingungen unterschiedliche rekursive Unteraufrufe verwendet und deren Ergebnisse zusammenführt oder wenn die Verzweigung komplexer ist. Und die Optimierung ist möglicherweise unnötig und den Aufwand überhaupt nicht wert.
Durch Rekursion kann ein kürzerer Code entstehen, der leichter zu verstehen und zu unterstützen ist. Optimierungen sind nicht an jeder Stelle erforderlich, meistens brauchen wir einen guten Code, deshalb wird er verwendet.
Eine weitere großartige Anwendung der Rekursion ist eine rekursive Durchquerung.
Stellen Sie sich vor, wir haben ein Unternehmen. Die Personalstruktur kann als Objekt dargestellt werden:
let company = {
Verkäufe: [{
Name: 'John',
Gehalt: 1000
}, {
Name: „Alice“,
Gehalt: 1600
}],
Entwicklung: {
Websites: [{
Name: 'Peter',
Gehalt: 2000
}, {
Name: 'Alex',
Gehalt: 1800
}],
Interna: [{
Name: 'Jack',
Gehalt: 1300
}]
}
};Mit anderen Worten: Ein Unternehmen hat Abteilungen.
Eine Abteilung kann über eine Reihe von Mitarbeitern verfügen. Die sales hat beispielsweise zwei Mitarbeiter: John und Alice.
Oder eine Abteilung kann in Unterabteilungen aufgeteilt werden, so wie development zwei Zweige hat: sites und internals . Jeder von ihnen hat sein eigenes Personal.
Es ist auch möglich, dass sich eine Unterabteilung, wenn sie wächst, in Unterabteilungen (oder Teams) aufteilt.
Beispielsweise könnte die sites künftig in Teams für siteA und siteB aufgeteilt werden. Und sie können möglicherweise noch mehr spalten. Das ist nicht auf dem Bild, sondern nur etwas, das man im Hinterkopf behalten sollte.
Nehmen wir nun an, wir möchten, dass eine Funktion die Summe aller Gehälter ermittelt. Wie können wir das machen?
Ein iterativer Ansatz ist nicht einfach, da die Struktur nicht einfach ist. Die erste Idee könnte darin bestehen, eine for Schleife über company mit einer verschachtelten Unterschleife über die Abteilungen der ersten Ebene zu erstellen. Aber dann brauchen wir mehr verschachtelte Unterschleifen, um die Mitarbeiter in Abteilungen der 2. Ebene wie sites zu durchlaufen … Und dann eine weitere Unterschleife innerhalb der Abteilungen der 3. Ebene, die möglicherweise in Zukunft erscheinen wird? Wenn wir 3-4 verschachtelte Unterschleifen in den Code einfügen, um ein einzelnes Objekt zu durchlaufen, wird es ziemlich hässlich.
Versuchen wir es mit der Rekursion.
Wie wir sehen können, gibt es zwei mögliche Fälle, wenn unsere Funktion eine Abteilung zum Summieren bringt:
Entweder handelt es sich um eine „einfache“ Abteilung mit einer Reihe von Mitarbeitern – dann können wir die Gehälter in einer einfachen Schleife summieren.
Oder es handelt sich um ein Objekt mit N Unterabteilungen – dann können wir N rekursive Aufrufe durchführen, um die Summe für jede der Unterabteilungen zu erhalten und die Ergebnisse zu kombinieren.
Der erste Fall ist die Basis der Rekursion, der triviale Fall, wenn wir ein Array erhalten.
Der zweite Fall, in dem wir ein Objekt erhalten, ist der rekursive Schritt. Eine komplexe Aufgabe wird in Teilaufgaben für kleinere Abteilungen aufgeteilt. Sie können sich abwechselnd wieder trennen, aber früher oder später wird die Trennung bei (1) enden.
Der Algorithmus ist wahrscheinlich noch einfacher aus dem Code zu lesen:
let company = { // das gleiche Objekt, der Kürze halber komprimiert
Umsatz: [{Name: 'John', Gehalt: 1000}, {Name: 'Alice', Gehalt: 1600 }],
Entwicklung: {
Websites: [{Name: 'Peter', Gehalt: 2000}, {Name: 'Alex', Gehalt: 1800 }],
Interna: [{Name: 'Jack', Gehalt: 1300}]
}
};
// Die Funktion, die den Job erledigt
Funktion sumSalaries(department) {
if (Array.isArray(department)) { // case (1)
return Department.reduce((prev, current) => prev + current.salary, 0); // Summiere das Array
} else { // case (2)
sei Summe = 0;
for (let subdep of Object.values(department)) {
sum += sumSalaries(subdep); // Unterabteilungen rekursiv aufrufen, Ergebnisse summieren
}
Rückgabesumme;
}
}
Alert(sumSalaries(company)); // 7700Der Code ist kurz und leicht verständlich (hoffentlich?). Das ist die Macht der Rekursion. Es funktioniert auch für jede Ebene der Unterabteilungsverschachtelung.
Hier ist das Diagramm der Anrufe:
Wir können das Prinzip leicht erkennen: Für ein Objekt {...} werden Unteraufrufe durchgeführt, während Arrays [...] die „Blätter“ des Rekursionsbaums sind, sie liefern unmittelbare Ergebnisse.
Beachten Sie, dass der Code intelligente Funktionen verwendet, die wir bereits behandelt haben:
Die Methode arr.reduce wird im Kapitel Array-Methoden erläutert, um die Summe des Arrays zu ermitteln.
Schleife for(val of Object.values(obj)) um über Objektwerte zu iterieren: Object.values gibt ein Array davon zurück.
Eine rekursive (rekursiv definierte) Datenstruktur ist eine Struktur, die sich in Teilen repliziert.
Wir haben es gerade oben am Beispiel einer Firmenstruktur gesehen.
Eine Unternehmensabteilung ist:
Entweder eine Reihe von Menschen.
Oder ein Objekt mit Abteilungen .
Für Webentwickler gibt es weitaus bekanntere Beispiele: HTML- und XML-Dokumente.
Im HTML-Dokument kann ein HTML-Tag eine Liste von Folgendem enthalten:
Textstücke.
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 behandeln wir eine weitere rekursive Struktur namens „Verknüpfte Liste“, die in manchen Fällen eine bessere Alternative für Arrays sein könnte.
Stellen Sie sich vor, wir möchten eine geordnete Liste von Objekten speichern.
Die natürliche Wahl wäre ein Array:
let arr = [obj1, obj2, obj3];
…Aber es gibt ein Problem mit Arrays. Die Vorgänge „Element löschen“ und „Element einfügen“ sind teuer. Beispielsweise muss die Operation arr.unshift(obj) alle Elemente neu nummerieren, um Platz für ein neues obj zu schaffen, und wenn das Array groß ist, braucht es Zeit. Das Gleiche 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 . Daher kann ein Array bei großen Warteschlangen recht 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 wä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.
Zum Beispiel:
let list = {
Wert: 1,
nächste: {
Wert: 2,
nächste: {
Wert: 3,
nächste: {
Wert: 4,
weiter: null
}
}
}
};Grafische Darstellung der Liste:
Ein alternativer Code zur Erstellung:
let list = { value: 1 };
list.next = { Wert: 2 };
list.next.next = { Wert: 3 };
list.next.next.next = { Wert: 4 };
list.next.next.next.next = null; Hier können wir noch deutlicher erkennen, dass es mehrere Objekte gibt, von denen jedes den value hat und next auf den Nachbarn zeigt. Die list ist das erste Objekt in der Kette. Wenn wir also next Zeigern von ihr folgen, können wir jedes Element erreichen.
Die Liste kann problemlos in mehrere Teile aufgeteilt und später wieder zusammengefügt werden:
let secondList = list.next.next; list.next.next = null;
Beitreten:
list.next.next = secondList;
Und natürlich können wir an jedem Ort Gegenstände einfügen oder entfernen.
Um beispielsweise einen neuen Wert voranzustellen, müssen wir den Kopf der Liste aktualisieren:
let list = { value: 1 };
list.next = { Wert: 2 };
list.next.next = { Wert: 3 };
list.next.next.next = { Wert: 4 };
// Den neuen Wert der Liste voranstellen
list = { value: "new item", next: list }; Um einen Wert aus der Mitte zu entfernen, ändern Sie next vom vorherigen:
list.next = list.next.next;
Wir haben list.next dazu gebracht, über 1 zum Wert 2 zu springen. Der Wert 1 ist nun aus der Kette ausgeschlossen. Wenn es nirgendwo anders gespeichert ist, wird es automatisch aus dem Speicher entfernt.
Im Gegensatz zu Arrays gibt es keine massenhafte Neunummerierung, wir können Elemente einfach neu anordnen.
Natürlich sind Listen nicht immer besser als Arrays. Sonst würde jeder nur Listen verwenden.
Der Hauptnachteil besteht darin, dass wir nicht einfach über seine Nummer auf ein Element zugreifen können. In einem Array ist das ganz einfach: arr[n] ist eine direkte Referenz. Aber in der Liste müssen wir mit dem ersten Element beginnen und N mal next 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 ein sehr schnelles Hinzufügen/Entfernen von Elementen an beiden Enden ermöglichen muss, aber keinen Zugriff auf die Mitte benötigt.
Listen können erweitert werden:
Wir können die Eigenschaft prev zusätzlich zur next hinzufügen, um auf das vorherige Element zu verweisen und so einfacher zurückzugehen.
Wir können auch eine Variable namens tail hinzufügen, die auf das letzte Element der Liste verweist (und sie aktualisieren, wenn Elemente am Ende hinzugefügt/entfernt werden).
…Die Datenstruktur kann je nach unseren Bedürfnissen variieren.
Bedingungen:
Rekursion ist ein Programmierbegriff, der den Aufruf einer Funktion aus sich selbst bezeichnet. Mit rekursiven Funktionen können Aufgaben auf elegante Weise gelöst werden.
Wenn eine Funktion sich selbst aufruft, spricht man von einem Rekursionsschritt . Grundlage der Rekursion sind Funktionsargumente, die die Aufgabe so einfach machen, dass die Funktion keine weiteren Aufrufe durchführt.
Eine rekursiv definierte Datenstruktur ist eine Datenstruktur, die über sich selbst definiert werden kann.
Beispielsweise kann die verknüpfte Liste 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 von Natur aus rekursiv: Sie haben Zweige und jeder Zweig kann andere Zweige haben.
Rekursive Funktionen können verwendet werden, um sie zu durchlaufen, wie wir im sumSalary -Beispiel gesehen haben.
Jede rekursive Funktion kann in eine iterative Funktion umgeschrieben werden. Und das ist manchmal erforderlich, um Dinge zu optimieren. Aber für viele Aufgaben ist eine rekursive Lösung schnell genug und einfacher zu schreiben und zu unterstützen.
Wichtigkeit: 5
Schreiben Sie eine Funktion sumTo(n) , die die Summe der Zahlen 1 + 2 + ... + n berechnet.
Zum Beispiel:
sumTo(1) = 1 sumTo(2) = 2 + 1 = 3 sumTo(3) = 3 + 2 + 1 = 6 sumTo(4) = 4 + 3 + 2 + 1 = 10 ... sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050
Machen Sie 3 Lösungsvarianten:
Verwendung einer for-Schleife.
Bewirken Sie mithilfe einer Rekursion, dass sumTo(n) = n + sumTo(n-1) für n > 1 ist.
Verwendung der arithmetischen Progressionsformel.
Ein Beispiel für das Ergebnis:
function sumTo(n) { /*... dein Code ... */ }
alarm( sumTo(100) ); // 5050PS: Welche Lösungsvariante ist die schnellste? Der langsamste? Warum?
PPS Können wir Rekursion verwenden, um sumTo(100000) zu zählen?
Die Lösung mit einer Schleife:
Funktion sumTo(n) {
sei Summe = 0;
for (sei i = 1; i <= n; i++) {
Summe += i;
}
Rückgabesumme;
}
alarm( sumTo(100) );Die Lösung mittels Rekursion:
Funktion sumTo(n) {
if (n == 1) return 1;
return n + sumTo(n - 1);
}
alarm( sumTo(100) ); Die Lösung mit der Formel: sumTo(n) = n*(n+1)/2 :
Funktion sumTo(n) {
return n * (n + 1) / 2;
}
alarm( sumTo(100) ); PS Natürlich ist die Formel die schnellste Lösung. Es verwendet nur 3 Operationen für jede Zahl n . Die Mathematik hilft!
Die Loop-Variante ist in puncto Geschwindigkeit die zweite. Sowohl in der rekursiven als auch in der Schleifenvariante summieren wir die gleichen Zahlen. Die Rekursion umfasst jedoch verschachtelte Aufrufe und die Verwaltung des Ausführungsstapels. Das verbraucht auch Ressourcen und ist daher langsamer.
PPS Einige Engines unterstützen die „Tail Call“-Optimierung: Wenn ein rekursiver Aufruf der allerletzte in der Funktion ist und keine anderen Berechnungen durchgeführt werden, muss die äußere Funktion die Ausführung nicht fortsetzen, sodass die Engine dies nicht tun muss Erinnern Sie sich an den Ausführungskontext. Das entlastet das Gedächtnis. Wenn die JavaScript-Engine jedoch die Tail-Call-Optimierung nicht unterstützt (was bei den meisten der Fall ist), wird ein Fehler angezeigt: „Maximale Stapelgröße überschritten“, da die Gesamtstapelgröße normalerweise begrenzt ist.
Wichtigkeit: 4
Die Fakultät einer natürlichen Zahl ist eine Zahl multipliziert mit "number minus one" , dann mit "number minus two" usw. bis 1 . Die Fakultät von n wird als n!
Wir können eine Definition von Fakultät wie folgt schreiben:
N! = n * (n - 1) * (n - 2) * ...*1
Werte der Fakultäten für verschiedene n :
1! = 1 2! = 2 * 1 = 2 3! = 3 * 2 * 1 = 6 4! = 4 * 3 * 2 * 1 = 24 5! = 5 * 4 * 3 * 2 * 1 = 120
Die Aufgabe besteht darin, eine Funktion factorial(n) zu schreiben, die n! Verwendung rekursiver Aufrufe.
alarm( faktorielle(5) ); // 120
PS Hinweis: n! kann als n * (n-1)! Zum Beispiel: 3! = 3*2! = 3*2*1! = 6
Per Definition ist ein faktorielles n! kann als n * (n-1)! .
Mit anderen Worten, das Ergebnis von factorial(n) kann als n multipliziert mit dem Ergebnis von factorial(n-1) berechnet werden. Und der Aufruf für n-1 kann rekursiv tiefer und tiefer absteigen, bis 1 .
Funktion Fakultät(n) {
return (n != 1) ? n * Fakultät(n - 1) : 1;
}
alarm( faktorielle(5) ); // 120 Die Basis der Rekursion ist der Wert 1 . Wir können hier auch 0 zur Basis machen, das spielt keine große Rolle, bietet aber einen weiteren rekursiven Schritt:
Funktion Fakultät(n) {
n zurückgeben? n * Fakultät(n - 1) : 1;
}
alarm( faktorielle(5) ); // 120Wichtigkeit: 5
Die Folge der Fibonacci-Zahlen hat die Formel F n = F n-1 + F n-2 . Mit anderen Worten: Die nächste Zahl ist eine Summe der beiden vorhergehenden.
Die ersten beiden Zahlen sind 1 , dann 2(1+1) , dann 3(1+2) , 5(2+3) und so weiter: 1, 1, 2, 3, 5, 8, 13, 21... .
Fibonacci-Zahlen hängen mit dem Goldenen Schnitt und vielen Naturphänomenen um uns herum zusammen.
Schreiben Sie eine Funktion fib(n) , die die n-th Fibonacci-Zahl zurückgibt.
Ein Arbeitsbeispiel:
Funktion fib(n) { /* Ihr Code */ }
alarm(fib(3)); // 2
alarm(fib(7)); // 13
alarm(fib(77)); // 5527939700884757 PS: Die Funktion sollte schnell sein. Der Aufruf von fib(77) sollte nicht länger als einen Bruchteil einer Sekunde dauern.
Die erste Lösung, die wir hier ausprobieren könnten, ist die rekursive.
Fibonacci-Zahlen sind per Definition rekursiv:
Funktion fib(n) {
n <= 1 zurückgeben? n: fib(n - 1) + fib(n - 2);
}
alarm( fib(3) ); // 2
alarm( fib(7) ); // 13
// fib(77); // wird extrem langsam sein! …Aber für große Werte von n ist es sehr langsam. Beispielsweise kann fib(77) dazu führen, dass die Engine für einige Zeit anhält und alle CPU-Ressourcen verbraucht.
Das liegt daran, dass die Funktion zu viele Unteraufrufe durchführt. Die gleichen Werte werden immer wieder neu bewertet.
Sehen wir uns zum Beispiel einen Teil der Berechnungen für fib(5) an:
... fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) ...
Hier können wir sehen, dass der Wert von fib(3) sowohl für fib(5) als auch für fib(4) benötigt wird. Daher wird fib(3) zwei Mal völlig unabhängig voneinander aufgerufen und ausgewertet.
Hier ist der vollständige Rekursionsbaum:
Wir können deutlich erkennen, dass fib(3) zweimal und fib(2) dreimal ausgewertet wird. Die Gesamtzahl der Berechnungen wächst viel schneller als n und ist selbst für n=77 enorm.
Wir können das optimieren, indem wir uns bereits ausgewertete Werte merken: Wenn ein Wert von beispielsweise fib(3) einmal berechnet wird, können wir ihn in zukünftigen Berechnungen einfach wiederverwenden.
Eine andere Variante wäre, auf die Rekursion zu verzichten und einen völlig anderen schleifenbasierten Algorithmus zu verwenden.
Anstatt von n zu niedrigeren Werten zu gehen, können wir eine Schleife erstellen, die bei 1 und 2 beginnt und dann fib(3) als deren Summe, dann fib(4) als die Summe zweier vorheriger Werte und dann fib(5) erhält. und steigt und steigt, bis der benötigte Wert erreicht ist. Bei jedem Schritt müssen wir uns nur zwei vorherige Werte merken.
Hier sind die Schritte des neuen Algorithmus im Detail.
Der Anfang:
// a = fib(1), b = fib(2), diese Werte sind per Definition 1 sei a = 1, b = 1; // c = fib(3) als Summe erhalten sei c = a + b; /* wir haben jetzt fib(1), fib(2), fib(3) a b c 1, 1, 2 */
Jetzt wollen wir fib(4) = fib(2) + fib(3) erhalten.
Verschieben wir die Variablen: a,b erhalten fib(2),fib(3) und c erhalten ihre Summe:
a = b; // jetzt a = fib(2) b = c; // jetzt b = fib(3) c = a + b; // c = fib(4) /* jetzt haben wir die Sequenz: a b c 1, 1, 2, 3 */
Der nächste Schritt gibt eine weitere Sequenznummer an:
a = b; // jetzt a = fib(3)
b = c; // jetzt b = fib(4)
c = a + b; // c = fib(5)
/* jetzt ist die Sequenz (eine weitere Zahl):
a b c
1, 1, 2, 3, 5
*/…Und so weiter, bis wir den benötigten Wert erhalten. Das ist viel schneller als die Rekursion und erfordert keine doppelten Berechnungen.
Der vollständige Code:
Funktion fib(n) {
sei a = 1;
sei b = 1;
for (sei i = 3; i <= n; i++) {
sei c = a + b;
a = b;
b = c;
}
Rückkehr b;
}
alarm( fib(3) ); // 2
alarm( fib(7) ); // 13
alarm( fib(77) ); // 5527939700884757 Die Schleife beginnt mit i=3 , da der erste und der zweite Sequenzwert in den Variablen a=1 , b=1 fest codiert sind.
Der Ansatz wird als dynamische Programmierung von unten nach oben bezeichnet.
Wichtigkeit: 5
Nehmen wir an, wir haben eine einfach verknüpfte Liste (wie im Kapitel Rekursion und Stapel beschrieben):
let list = {
Wert: 1,
nächste: {
Wert: 2,
nächste: {
Wert: 3,
nächste: {
Wert: 4,
weiter: null
}
}
}
}; Schreiben Sie eine Funktion printList(list) die Listenelemente einzeln ausgibt.
Machen Sie zwei Varianten der Lösung: Verwenden einer Schleife und Verwenden einer Rekursion.
Was ist besser: mit Rekursion oder ohne?
Die schleifenbasierte Variante der Lösung:
let list = {
Wert: 1,
nächste: {
Wert: 2,
nächste: {
Wert: 3,
nächste: {
Wert: 4,
weiter: null
}
}
}
};
Funktion printList(list) {
let tmp = list;
while (tmp) {
alarm(tmp.value);
tmp = tmp.next;
}
}
printList(list); Bitte beachten Sie, dass wir zum Durchlaufen der Liste eine temporäre Variable tmp verwenden. Technisch gesehen könnten wir stattdessen eine list verwenden:
Funktion printList(list) {
while(list) {
alarm(list.value);
list = list.next;
}
} …Aber das wäre unklug. In Zukunft müssen wir möglicherweise eine Funktion erweitern oder etwas anderes mit der Liste tun. Wenn wir list ändern, verlieren wir diese Fähigkeit.
Apropos gute Variablennamen: list hier ist die Liste selbst. Das erste Element davon. Und das soll auch so bleiben. Das ist klar und zuverlässig.
Auf der anderen Seite besteht die Rolle von tmp ausschließlich darin, eine Liste zu durchlaufen, wie i in der for Schleife.
Die rekursive Variante von printList(list) folgt einer einfachen Logik: Um eine Liste auszugeben, sollten wir das aktuelle Element list ausgeben und dann dasselbe für list.next tun:
let list = {
Wert: 1,
nächste: {
Wert: 2,
nächste: {
Wert: 3,
nächste: {
Wert: 4,
weiter: null
}
}
}
};
Funktion printList(list) {
alarm(list.value); // das aktuelle Element ausgeben
if (list.next) {
printList(list.next); // Machen Sie dasselbe für den Rest der Liste
}
}
printList(list);Was ist nun besser?
Technisch gesehen ist die Schleife effektiver. Diese beiden Varianten machen dasselbe, aber die Schleife verbraucht keine Ressourcen für verschachtelte Funktionsaufrufe.
Andererseits ist die rekursive Variante kürzer und manchmal einfacher zu verstehen.
Wichtigkeit: 5
Eine einfach verknüpfte Liste aus der vorherigen Aufgabe ausgeben. Eine einfach verknüpfte Liste in umgekehrter Reihenfolge ausgeben.
Machen Sie zwei Lösungen: Verwenden einer Schleife und Verwenden einer Rekursion.
Die rekursive Logik ist hier etwas knifflig.
Wir müssen zuerst den Rest der Liste ausgeben und dann die aktuelle ausgeben:
let list = {
Wert: 1,
nächste: {
Wert: 2,
nächste: {
Wert: 3,
nächste: {
Wert: 4,
weiter: null
}
}
}
};
Funktion printReverseList(list) {
if (list.next) {
printReverseList(list.next);
}
alarm(list.value);
}
printReverseList(list);
Die Loop-Variante ist auch etwas komplizierter als die direkte Ausgabe.
Es gibt keine Möglichkeit, den letzten Wert in unserer list abzurufen. Wir können auch nicht „zurückgehen“.
Was wir also tun können, ist, die Elemente zunächst in direkter Reihenfolge durchzugehen und sie in einem Array zu speichern und dann das, was wir uns gemerkt haben, in umgekehrter Reihenfolge auszugeben:
let list = {
Wert: 1,
nächste: {
Wert: 2,
nächste: {
Wert: 3,
nächste: {
Wert: 4,
weiter: null
}
}
}
};
Funktion printReverseList(list) {
sei arr = [];
let tmp = list;
while (tmp) {
arr.push(tmp.value);
tmp = tmp.next;
}
for (let i = arr.length - 1; i >= 0; i--) {
alarm( arr[i] );
}
}
printReverseList(list);Bitte beachten Sie, dass die rekursive Lösung tatsächlich genau das Gleiche tut: Sie folgt der Liste, merkt sich die Elemente in der Kette verschachtelter Aufrufe (im Ausführungskontextstapel) und gibt sie dann aus.