Die Funktion ruft sich selbst auf, bis jemand sie stoppt.
Rekursion kann sich für neue Entwickler schwierig anfühlen. Vielleicht liegt das daran, dass viele Ressourcen es anhand algorithmischer Beispiele (Fibonacci, verknüpfte Listen) lehren. Dieses Stück wird hoffentlich anhand eines einfachen Beispiels die Dinge klar einführen.
Kernidee
Rekursion ist, wenn sich eine Funktion selbst aufruft, bis jemand sie stoppt. Wenn niemand es aufhält, wird es für immer wiederkehren (sich selbst nennen).
Mit rekursiven Funktionen können Sie eine Arbeitseinheit mehrmals ausführen. Genau das können for/while
wir mit Loops erreichen! Manchmal sind rekursive Lösungen jedoch ein eleganterer Ansatz zur Lösung eines Problems.
Countdown-Funktion
Lassen Sie uns eine Funktion erstellen, die von einer bestimmten Zahl herunterzählt. Wir werden es so verwenden.
countDownFrom(5); // 5 // 4 // 3 // 2 // 1
Und hier ist unser Algorithmus, um dieses Problem zu lösen.
- Nehmen Sie einen Parameter namens
number
. Dies ist unser Ausgangspunkt. - Gehen Sie von
number
unten nach unten0
und protokollieren Sie jeden auf dem Weg.
Wir beginnen mit einem for
Loop-Ansatz und vergleichen ihn dann mit einem rekursiven.
Imperativer Ansatz (Schleifen)
function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); } } countDownFrom(5); // 5 // 4 // 3 // 2 // 1
Dieser enthält beide algorithmischen Schritte.
- ✅ Nehmen Sie einen Parameter namens
number
. - ✅ Protokolliere alles von
number
bis0
.
Rekursiver Ansatz
function countDownFrom(number) { if (number === 0) { return; } console.log(number); countDownFrom(number - 1); } countDownFrom(5); // 5 // 4 // 3 // 2 // 1
Dieser geht auch vorbei.
- ✅ Nehmen Sie einen Parameter namens
number
. - ✅ Protokolliere alles von
number
bis0
.
Konzeptionell sind die beiden Ansätze also gleich. Sie erledigen die Arbeit jedoch auf unterschiedliche Weise.
Debuggen unserer zwingenden Lösung
Als visuelleres Beispiel fügen wir eine debugger
in unsere Loop-Version ein und werfen sie in die Chrome Developer Tools.
function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); debugger; } }
Sehen Sie, wie eine zusätzliche Variable verwendet wird i
, um die aktuelle Nummer zu verfolgen? Während Sie iterieren, i
nimmt die Anzahl ab und wird schließlich getroffen 0
und beendet.
Und in der for
Schleife haben wir "stop if i > 0
" angegeben.
Debuggen unserer rekursiven Lösung
function countDownFrom(number) { if (number === 0) { return; } console.log(number); debugger; countDownFrom(number - 1); }
Die rekursive Version benötigt keine zusätzlichen Variablen, um den Fortschritt zu verfolgen. Beachten Sie, wie der Stapel von Funktionen ( Aufrufstapel ) wächst, wenn wir wiederkehren?
Das liegt daran, dass jeder Aufruf zum countDownFrom
Stack hinzugefügt wird und ihn füttert number - 1
. Auf diese Weise geben wir number
jedes Mal eine Aktualisierung weiter . Kein zusätzlicher Zustand erforderlich!
Das ist der Hauptunterschied zwischen den beiden Ansätzen.
- Iterativ verwendet den internen Zustand (zusätzliche Variablen zum Zählen usw.).
- Rekursiv nicht, es werden einfach aktualisierte Parameter zwischen jedem Aufruf übergeben.
Aber woher weiß eine der Versionen, wann sie aufhören sollen?
Endlosschleifen
Auf Ihren Reisen wurden Sie möglicherweise vor der gefürchteten Endlosschleife gewarnt.
? THIS RUNS FOREVER, BE WARNED ? while (true) { console.log('WHY DID YOU RUN THIS?!' } ? THIS RUNS FOREVER, BE WARNED ? for (i = 0;;) { console.log('WHY DID YOU RUN THIS?!') }
Da sie theoretisch für immer laufen würden, stoppt eine Endlosschleife Ihr Programm und stürzt möglicherweise Ihren Browser ab. Sie können sie verhindern, indem Sie immer eine Stoppbedingung codieren .
✅ This does not run forever x = 0; while (x < 3) { console.log(x); x++; } ✅ This does not run forever for (x = 0; x < 3; x++) { console.log(x); }
In beiden Fällen protokollieren wir x
, erhöhen es und stoppen, wenn es wird 3
. Unsere countDownFrom
Funktion hatte eine ähnliche Logik.
// Stop at 0 for (let i = number; i > 0; i--)
Auch hier benötigen Schleifen einen zusätzlichen Status, um zu bestimmen, wann sie gestoppt werden sollen. Das ist was x
und i
sind dafür.
Unendliche Rekursion
Rekursion birgt auch die gleiche Gefahr. Es ist nicht schwer, eine selbstreferenzierende Funktion zu schreiben, die Ihren Browser zum Absturz bringt.
?THIS RUNS FOREVER, BE WARNED? function run() { console.log('running'); run(); } run(); // running // running // ...
Without a stopping condition, run
will forever call itself. You can fix that with an if
statement.
✅ This does not run forever function run(x) { if (x === 3) return; console.log('running'); run(x + 1); } run(0); // running // running // running // x is 3 now, we're done.
Base case
This is known as the base case–our recursive countDownFrom
had one.
if (number === 0) { return; }
It's the same idea as our loop's stopping logic. Whichever approach you pick, always remember that at some point it needs to be stopped.
Summary
- Recursion is when a function calls itself until someone stops it.
- It can be used instead of a loop.
- If no one stops it, it'll recurse forever and crash your program.
- A base case is a condition that stops the recursion. Don't forget to add them!
- Loops use extra state variables for tracking and counting, while recursion only uses the provided parameters.
Thanks for reading
Weitere Inhalte wie diesen finden Sie unter //yazeedb.com. Und bitte lassen Sie mich wissen, was Sie sonst noch sehen möchten! Meine DMs sind auf Twitter geöffnet.
Bis zum nächsten Mal!