Kratki uvod u rekurziju u Javascriptu

Programiranje

Funkcija se poziva dok je netko ne zaustavi.

Rekurzija može biti teška za nove programere. Možda je to zato što ga mnogi resursi podučavaju koristeći algoritamske primjere (Fibonacci, povezani popisi). Nadam se da će ovaj dio na jednostavan primjer predstaviti stvari na jednostavan način.

Osnovna ideja

Rekurzija je kada se funkcija poziva dok je netko ne zaustavi. Ako ga nitko ne zaustavi, zauvijek će se ponoviti (nazvati).

no-this-is-patrick

Rekurzivne funkcije omogućuju vam obavljanje jedinice rada više puta. To je upravo ono što for/whilenam petlje omogućuju! Međutim, ponekad su rekurzivna rješenja elegantniji pristup rješavanju problema.

Funkcija odbrojavanja

Stvorimo funkciju koja odbrojava od zadanog broja. Koristit ćemo ga ovako.

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

I evo našeg algoritma za rješavanje ovog problema.

  1. Uzmi jedan parametar koji se zove number. Ovo je naše polazište.
  2. Idite od numberdolje 0, bilježeći svakoga usput.

Započet ćemo s forpristupom petlje, a zatim ćemo ga usporediti s rekurzivnim.

Imperativni pristup (petlje)

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

Ovaj sadrži oba algoritamska koraka.

  1. ✅ Uzmite jedan pozvani parametar number.
  2. ✅ Zabilježite sve od numberdo 0.

Rekurzivni pristup

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

Prolazi i ovaj.

  1. ✅ Uzmite jedan pozvani parametar number.
  2. ✅ Zabilježite sve od numberdo 0.

Dakle, konceptualno su dva pristupa ista. Međutim, posao obavljaju na različite načine.

Otklanjanje pogrešaka s našeg imperativnog rješenja

Za vizualniji primjer stavimo debuggerverziju s petljom i bacimo je u Chrome Developer Tools.

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

odbrojavanjeOd iterativnog

Pogledajte kako koristi dodatnu varijablu i, za praćenje trenutnog broja? Kako se ponavljate, ismanjuje se, na kraju udara 0i završava.

I u forpetlji smo naveli "zaustavi ako i > 0".

Otklanjanje pogrešaka u našem rekurzivnom rješenju

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

odbrojavanjeOd rekurzivnog

Rekurzivna verzija ne treba dodatne varijable za praćenje napretka. Primijetite kako gomila funkcija ( hrpa poziva ) raste kako se ponavljamo?

To je zato što se svaki poziv na countDownFromdodaje na hrpu, hrani je number - 1. Čineći to, numbersvaki put prolazimo s ažuriranim podacima. Nije potrebna dodatna država!

To je glavna razlika između dva pristupa.

  1. Iterative koristi unutarnje stanje (dodatne varijable za brojanje, itd.).
  2. Rekurzivno ne, jednostavno prenosi ažurirane parametre između svakog poziva.

Ali kako bilo koja verzija zna kada treba stati?

Beskonačne petlje

U svojim putovanjima možda ste bili upozoreni na strašnu beskonačnu petlju.

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

Budući da bi teoretski radili zauvijek, beskonačna petlja zaustavit će vaš program i možda srušiti vaš preglednik. Možete ih spriječiti tako da uvijek kodirate uvjet zaustavljanja .

✅ 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); }

U oba slučaja bilježimo se x, povećavamo ga i zaustavljamo kad postane 3. Naša je countDownFromfunkcija imala sličnu logiku.

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

Opet, petlje trebaju dodatno stanje kako bi odredile kada bi se trebale zaustaviti. To je ono što xi čemu isluži.

Beskonačna rekurzija

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

je-ovo-rekurzivno

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.

je-li-ovo-vas-treba-zaustaviti

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!
  • Petlje koriste dodatne varijable stanja za praćenje i brojanje, dok rekurzija koristi samo navedene parametre.

petlje nestajanja

Hvala na čitanju

Za više ovakvih sadržaja pogledajte //yazeedb.com. I molim vas, javite mi što biste još željeli vidjeti! Moji su DM-i otvoreni na Twitteru.

Do sljedećeg puta!