En hurtig introduktion til rekursion i Javascript

Funktionen kalder sig selv, indtil nogen stopper den.

Rekursion kan føles vanskeligt for nye udviklere. Måske skyldes det, at mange ressourcer lærer det ved hjælp af algoritmiske eksempler (Fibonacci, linked-lists). Dette stykke vil forhåbentlig introducere tingene tydeligt ved hjælp af et simpelt eksempel.

Kerneide

Rekursion er, når en funktion kalder sig selv, indtil nogen stopper den. Hvis ingen stopper det, genopretter det (kalder sig selv) for evigt.

nej-dette-er-patrick

Rekursive funktioner giver dig mulighed for at udføre en arbejdsenhed flere gange. Dette er præcis, hvad for/whilesløjfer lader os udrette! Nogle gange er rekursive løsninger imidlertid en mere elegant tilgang til løsning af et problem.

Nedtællingsfunktion

Lad os oprette en funktion, der tæller ned fra et givet tal. Vi bruger det sådan.

countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

Og her er vores algoritme til at løse dette problem.

  1. Tag en parameter kaldet number. Dette er vores udgangspunkt.
  2. Gå fra numberned til 0, logge hver enkelt undervejs.

Vi starter med en forloop-tilgang og sammenligner den derefter med en rekursiv.

Imperativ tilgang (sløjfer)

function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); } } countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

Denne indeholder begge algoritmiske trin.

  1. ✅ Tag en parameter kaldet number.
  2. Log alt fra numbertil 0.

Rekursiv tilgang

function countDownFrom(number) { if (number === 0) { return; } console.log(number); countDownFrom(number - 1); } countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

Denne passerer også.

  1. ✅ Tag en parameter kaldet number.
  2. Log alt fra numbertil 0.

Så konceptuelt er de to tilgange de samme. De får dog arbejdet udført på forskellige måder.

Fejlretning af vores tvingende løsning

For et mere visuelt eksempel, lad os sætte en debuggeri vores loop-version og smide den i Chrome Developer Tools.

function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); debugger; } } 

nedtællingFra-iterativ

Se hvordan det bruger en ekstra variabel`` itil at spore det aktuelle nummer? Efterhånden som du gentager sig, ifalder og til sidst rammer 0og afsluttes.

Og i forsløjfen specificerede vi "stop if i > 0".

Fejlfinding af vores rekursive løsning

function countDownFrom(number) { if (number === 0) { return; } console.log(number); debugger; countDownFrom(number - 1); } 

nedtællingFra-rekursiv

Den rekursive version har ikke brug for ekstra variabler for at spore dens fremskridt. Læg mærke til, hvordan bunken af ​​funktioner ( opkaldstak ) vokser, når vi recirkuerer?

Det skyldes, at hvert opkald, der countDownFromføjes til stakken, føder det number - 1. Ved at gøre dette passerer vi en opdateret numberhver gang. Ingen ekstra tilstand nødvendig!

Det er den største forskel mellem de to tilgange.

  1. Iterative uses internal state (extra variables for counting, etc).
  2. Recursive does not, it simply passes updated parameters between each call.

But how does either version know when to stop?

Infinite Loops

In your travels, you may have been warned about the dreaded infinite loop.

? 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?!') } 

Since they'd theoretically run forever, an infinite loop will halt your program and possibly crash your browser. You can prevent them by always coding a stopping condition.

✅ 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 both cases we log x, increment it, and stop when it becomes 3. Our countDownFrom function had similar logic.

// Stop at 0 for (let i = number; i > 0; i--) 

Again, loops need extra state to determine when they should stop. That's what x and i are for.

Infinite Recursion

Recursion also presents the same danger. It's not hard to write a self-referencing function that'll crash your browser.

?THIS RUNS FOREVER, BE WARNED? function run() { console.log('running'); run(); } run(); // running // running // ... 

er-dette-en-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.

er-dette-du-har brug for at blive stoppet

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!
  • Sløjfer bruger ekstra tilstandsvariabler til sporing og tælling, mens rekursion kun bruger de angivne parametre.

forsvindende sløjfer

Tak for læsningen

For mere indhold som dette, se //yazeedb.com. Og lad mig vide, hvad du ellers gerne vil se! Mine DM'er er åbne på Twitter.

Indtil næste gang!