Eine kurze Einführung in die Rekursion in Javascript

Programmierung

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).

Nein das ist Patrick

Mit rekursiven Funktionen können Sie eine Arbeitseinheit mehrmals ausführen. Genau das können for/whilewir 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.

  1. Nehmen Sie einen Parameter namens number. Dies ist unser Ausgangspunkt.
  2. Gehen Sie von numberunten nach unten 0und protokollieren Sie jeden auf dem Weg.

Wir beginnen mit einem forLoop-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.

  1. ✅ Nehmen Sie einen Parameter namens number.
  2. ✅ Protokolliere alles von numberbis 0.

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.

  1. ✅ Nehmen Sie einen Parameter namens number.
  2. ✅ Protokolliere alles von numberbis 0.

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 debuggerin 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; } }

countdownVon iterativ

Sehen Sie, wie eine zusätzliche Variable verwendet wird i, um die aktuelle Nummer zu verfolgen? Während Sie iterieren, inimmt die Anzahl ab und wird schließlich getroffen 0und beendet.

Und in der forSchleife 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); }

countdownFrom-rekursiv

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 countDownFromStack hinzugefügt wird und ihn füttert number - 1. Auf diese Weise geben wir numberjedes Mal eine Aktualisierung weiter . Kein zusätzlicher Zustand erforderlich!

Das ist der Hauptunterschied zwischen den beiden Ansätzen.

  1. Iterativ verwendet den internen Zustand (zusätzliche Variablen zum Zählen usw.).
  2. 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 countDownFromFunktion 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 xund isind 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 // ...

ist-das-ein-rekursiv

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.

ist-das-du-musst-gestoppt werden

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.

Verschwinden-Schleifen

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!