Rekursion ist nicht schwer: Eine schrittweise Anleitung dieser nützlichen Programmiertechnik

Ich werde das sofort sagen. Kennen Sie die Ereignisse, die beim Funktionsaufruf auftreten? Nein? Dann fangen wir dort an.

Funktionsaufruf

Wenn wir eine Funktion aufrufen, wird ein Ausführungskontext auf dem Ausführungsstapel platziert. Lassen Sie uns das noch etwas aufschlüsseln.

Was ist ein Stapel?

Ein Stack ist eine Datenstruktur, die auf der Basis von "Last In, First Out" arbeitet. Ein Gegenstand wird auf einen Stapel „geschoben“, um ihn hinzuzufügen, und ein Gegenstand wird vom Stapel „herausgesprungen“, um ihn zu entfernen.

Die Verwendung eines Stapels ist eine Methode zum Bestellen bestimmter Operationen zur Ausführung.

Zurück zu dem, was ein Ausführungskontext ist. Ein Ausführungskontext bildet sich bei einem Funktionsaufruf. Dieser Kontext platziert sich auf einem Ausführungsstapel, einer Reihenfolge von Operationen. Das Element, das in diesem Stapel immer an erster Stelle steht, ist der globale Ausführungskontext. Als nächstes werden alle von Funktionen erstellten Kontexte angezeigt.

Diese Ausführungskontexte haben Eigenschaften, ein Aktivierungsobjekt und eine "this" -Bindung. Die "this" -Bindung ist ein Verweis zurück auf diesen Ausführungskontext. Das Aktivierungsobjekt enthält: übergebene Parameter, deklarierte Variablen und Funktionsdeklarationen.

Jedes Mal, wenn wir einen neuen Kontext auf den Stapel legen, haben wir normalerweise alles, was wir zum Ausführen von Code benötigen.

Warum sage ich normalerweise ?

Bei der Rekursion warten wir auf Rückgabewerte aus anderen Ausführungskontexten. Diese anderen Kontexte befinden sich weiter oben im Stapel. Wenn das letzte Element auf dem Stapel die Ausführung beendet hat, generiert dieser Kontext einen Rückgabewert. Dieser Rückgabewert wird als Rückgabewert vom rekursiven Fall an das nächste Element weitergegeben. Dieser Ausführungskontext wird dann vom Stapel entfernt.

Rekursion

Was ist Rekursion?

Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft, bis eine „Grundbedingung“ erfüllt ist und die Ausführung gestoppt wird.

Während false, werden wir weiterhin Ausführungskontexte auf dem Stapel platzieren. Dies kann passieren, bis wir einen „Stapelüberlauf“ haben. Ein Stapelüberlauf liegt vor, wenn nicht mehr genügend Speicher vorhanden ist, um Elemente im Stapel zu speichern.

Im Allgemeinen besteht eine rekursive Funktion aus mindestens zwei Teilen: einer Grundbedingung und mindestens einem rekursiven Fall.

Schauen wir uns ein klassisches Beispiel an.

Fakultät

const factorial = function(num) { debugger; if (num === 0 || num === 1) { return 1 } else { return num * factorial(num - 1) }}
factorial(5)

Hier versuchen wir 5 zu finden! (fünf Fakultäten). Die Fakultätsfunktion ist definiert als das Produkt aller positiven ganzen Zahlen, die kleiner oder gleich ihrem Argument sind.

Die erste Bedingung lautet: "Wenn der übergebene Parameter gleich 0 oder 1 ist, werden wir beenden und 1 zurückgeben."

Als nächstes heißt es im rekursiven Fall:

"Wenn der Parameter nicht 0 oder 1 ist, übergeben wir den Wert des numRückgabewerts beim erneuten Aufrufen dieser Funktion num-1als Argument."

Wenn wir also aufrufen factorial(0), gibt die Funktion 1 zurück und trifft niemals den rekursiven Fall.

Gleiches gilt für factorial(1).

Wir können sehen, was passiert, wenn wir eine Debugger-Anweisung in den Code einfügen und devtools verwenden, um sie zu durchlaufen und den Aufrufstapel zu beobachten.

  1. Der Ausführungsstapel setzt factorial()5 als übergebenes Argument. Der Basisfall ist falsch, geben Sie also die rekursive Bedingung ein.
  2. Der Ausführungsstapel platziert factorial()ein zweites Mal mit num-1= 4 als Argument. Der Basisfall ist falsch. Geben Sie die rekursive Bedingung ein.
  3. Der Ausführungsstapel platziert factorial()ein drittes Mal mit num-1(4–1) = 3 als Argument. Der Basisfall ist falsch. Geben Sie die rekursive Bedingung ein.
  4. Der Ausführungsstapel platziert factorial()ein viertes Mal mit num-1(3–1) = 2 als Argument. Der Basisfall ist falsch. Geben Sie die rekursive Bedingung ein.
  5. Der Ausführungsstapel platziert factorial()ein fünftes Mal mit num-1(2–1) = 1 als Argument. Jetzt ist der Basisfall wahr, also geben Sie 1 zurück.

Zu diesem Zeitpunkt haben wir das Argument bei jedem Funktionsaufruf um eins verringert, bis wir eine Bedingung für die Rückgabe von 1 erreicht haben.

6. Von hier aus wird der letzte Ausführungskontext abgeschlossen num === 1, sodass die Funktion 1 zurückgibt.

7. Als nächstes num === 2ist der Rückgabewert 2. (1 × 2).

8. Als nächstes num === 3beträgt der Rückgabewert 6 (2 × 3).

Bisher haben wir 1 × 2 × 3.

9. Als nächstes num === 4(4 × 6). 24 ist der Rückgabewert zum nächsten Kontext.

10. Schließlich num === 5(5 × 24) und wir haben 120 als Endwert.

Rekursion ist ziemlich ordentlich, oder?

Wir hätten dasselbe mit einer for- oder einer while-Schleife machen können. Die Verwendung von Rekursion ergibt jedoch eine elegante Lösung, die besser lesbar ist.

Deshalb verwenden wir rekursive Lösungen.

Oft ist ein in kleinere Teile zerlegtes Problem effizienter. Die Aufteilung eines Problems in kleinere Teile hilft bei der Überwindung. Rekursion ist daher ein Divide-and-Conquer-Ansatz zur Lösung von Problemen.

  • Unterprobleme sind einfacher zu lösen als das ursprüngliche Problem
  • Lösungen für Unterprobleme werden kombiniert, um das ursprüngliche Problem zu lösen

"Teilen und Erobern" wird am häufigsten verwendet, um Datenstrukturen wie binäre Suchbäume, Diagramme und Haufen zu durchlaufen oder zu durchsuchen. Es funktioniert auch für viele Sortieralgorithmen wie Quicksort und Heapsort.

Lassen Sie uns die folgenden Beispiele durcharbeiten. Verwenden Sie devtools, um einen konzeptionellen Überblick darüber zu erhalten, was wo und wann passiert. Denken Sie daran, Debugger-Anweisungen zu verwenden und jeden Prozess zu durchlaufen.

Fibonacci

const fibonacci = function(num) { if (num <= 1) { return num } else { return fibonacci(num - 1) + fibonacci(num - 2) }}fibonacci(5);

Rekursive Arrays

function flatten(arr) { var result = [] arr.forEach(function(element) { if (!Array.isArray(element)) { result.push(element) } else { result = result.concat(flatten(element)) } }) return result}
flatten([1, [2], [3, [[4]]]]);

String umkehren

function reverse(str) { if (str.length === 0) return '' return str[str.length - 1] + reverse(str.substr(0, str.length - 1))}
reverse('abcdefg');

Schnelle Sorte

function quickSort(arr, lo, hi) { if (lo === undefined) lo = 0 if (hi === undefined) hi = arr.length - 1
 if (lo  partition: ' + p) // sort subarrays quickSort(arr, lo, p - 1) quickSort(arr, p + 1, hi) } // for initial call, return a sorted array if (hi - lo === arr.length - 1) return arr}
function partition(arr, lo, hi) { // choose last element as pivot var pivot = arr[hi] // keep track of index to put pivot at var pivotLocation = lo // loop through subarray and if element <= pivot, place element before pivot for (var i = lo; i < hi; i++) { if (arr[i] <= pivot) { swap(arr, pivotLocation, i) pivotLocation++ } } swap(arr, pivotLocation, hi) return pivotLocation}
function swap(arr, index1, index2) { if (index1 === index2) return var temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp console.log('swapped' + arr[index1], arr[index2], +' in ', arr) return arr}
quickSort([1, 4, 3, 56, 9, 8, 7, 5])

Das Üben rekursiver Techniken ist wichtig. Für verschachtelte Datenstrukturen wie Bäume, Diagramme und Heaps ist die Rekursion von unschätzbarem Wert.

In einem zukünftigen Artikel werde ich Tail-Call-Optimierungs- und Memoisierungstechniken diskutieren, die sich auf die Rekursion beziehen. Danke fürs Lesen!

Weitere Ressourcen

Wikipedia

Softwareentwicklung

Ein weiterer guter Artikel

MIT offene Kursunterlagen