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).
Rekurzivne funkcije omogućuju vam obavljanje jedinice rada više puta. To je upravo ono što for/while
nam 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.
- Uzmi jedan parametar koji se zove
number
. Ovo je naše polazište. - Idite od
number
dolje0
, bilježeći svakoga usput.
Započet ćemo s for
pristupom 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.
- ✅ Uzmite jedan pozvani parametar
number
. - ✅ Zabilježite sve od
number
do0
.
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.
- ✅ Uzmite jedan pozvani parametar
number
. - ✅ Zabilježite sve od
number
do0
.
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 debugger
verziju s petljom i bacimo je u Chrome Developer Tools.
function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); debugger; } }
Pogledajte kako koristi dodatnu varijablu i
, za praćenje trenutnog broja? Kako se ponavljate, i
smanjuje se, na kraju udara 0
i završava.
I u for
petlji 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); }
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 countDownFrom
dodaje na hrpu, hrani je number - 1
. Čineći to, number
svaki put prolazimo s ažuriranim podacima. Nije potrebna dodatna država!
To je glavna razlika između dva pristupa.
- Iterative koristi unutarnje stanje (dodatne varijable za brojanje, itd.).
- 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 countDownFrom
funkcija 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 x
i čemu i
služ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 // ...
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!
- Petlje koriste dodatne varijable stanja za praćenje i brojanje, dok rekurzija koristi samo navedene parametre.
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!