Kako funkcionira rekurzija - objašnjeno dijagramima toka i video zapisom

"Da bismo razumjeli rekurziju, prvo moramo razumjeti rekurziju."

Rekurziju može biti teško razumjeti - posebno za nove programere. U svom najjednostavnijem obliku rekurzivna je funkcija ona koja se sama poziva. Dopustite mi da pokušam objasniti na primjeru.

Zamislite da odete otvoriti vrata svoje spavaće sobe i zaključana su. Vaš trogodišnji sin uskače iza ugla i daje vam do znanja da je sakrio jedini ključ u kutiji. ("Baš poput njega", mislite.) Kasnite na posao i stvarno morate ući u sobu po košulju.

Otvorite okvir samo da biste pronašli ... još okvira. Kutije unutar kutija. I ne znate koja ima ključ! Morate uskoro dobiti tu košulju, pa morate smisliti dobar algoritam kako biste pronašli taj ključ.

Postoje dva glavna pristupa stvaranju algoritma za ovaj problem: iterativni i rekurzivni. Evo oba pristupa kao grafikoni tijeka:

Koji vam se pristup čini lakšim?

Prvi pristup koristi while petlju. Dok hrpa nije prazna, uzmite kutiju i pogledajte kroz nju. Evo nekoliko pseudokodova nadahnutih JavaScriptom koji pokazuju što se događa. (Pseudocode je napisan poput koda, ali trebao je biti više poput ljudskog govora.)

function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } }}

Drugi način koristi rekurziju. Zapamtite, rekurzija je mjesto gdje se funkcija poziva. Evo drugog načina u pseudokodu.

function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }

Oba pristupa postižu istu stvar. Glavna svrha korištenja rekurzivnog pristupa je da nakon što ga razumijete, bude jasnije čitati. Zapravo nema koristi od performansi korištenja rekurzije. Iterativni pristup s petljama ponekad može biti brži. Ali uglavnom se preferira jednostavnost rekurzije.

Također, budući da mnogi algoritmi koriste rekurziju, važno je razumjeti kako to funkcionira. Ako vam se rekurzija i dalje ne čini jednostavnom, ne brinite: pregledat ću još nekoliko primjera.

Osnovni slučaj i rekurzivni slučaj

Nešto na što morate paziti prilikom pisanja rekurzivne funkcije je beskonačna petlja. Tada se funkcija neprestano poziva ... i nikad se ne prestaje pozivati!

Na primjer, možda ćete htjeti napisati funkciju odbrojavanja. Možete to napisati rekurzivno na JavaScriptu ovako:

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1)} countdown(5); // This is the initial call to the function.

Ova će funkcija neprestano odbrojavati. Ako slučajno pokrenete kôd s beskonačnom petljom, možete pritisnuti "Ctrl-C" da biste ubili skriptu. (Ili, ako ponekad koristite CodePen poput mene, na kraj URL-a morate dodati "? Turn_off_js = true".)

Rekurzivna funkcija uvijek mora reći kada se prestati ponavljati. Uvijek bi trebala postojati dva dijela rekurzivne funkcije: rekurzivni slučaj i osnovni slučaj. Rekurzivni slučaj je kada se funkcija sama poziva. Osnovni slučaj je kada se funkcija prestaje sama pozivati. To sprječava beskonačne petlje.

Evo opet funkcije odbrojavanja, s osnovnim slučajem:

function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1); } } countdown(5); // This is the initial call to the function.

Možda nije očito što se točno događa u ovoj funkciji. Proći ću kroz ono što se događa kad nazovete funkciju odbrojavanja i prebacite u "5".

Započinjemo ispisom broja 5 pomoću console.log. Budući da pet nije manje ili jednako nuli, idemo na iskaz else. Tamo ponovno pozivamo funkciju odbrojavanja s brojem četiri (5–1 = 4?).

Mi se prijaviti na broj 4. Opet ise ne manje od ili jednaka nuli pa idemo u drugi izjava i poziva odbrojavanja s 3. To se nastavlja sve dokijednako nuli. Kada se to dogodi, zabilježimo broj nula i tada ije manji ili jednak nuli. Napokon dolazimo do izjave return i iskačemo iz funkcije.

Skup poziva

Rekurzivne funkcije koriste nešto što se naziva "skup poziva". Kada program pozove funkciju, ta funkcija prelazi na vrh snopa poziva. Ovo je slično hrpi knjiga. Dodajete stvari jednu po jednu. Tada, kad ste spremni nešto skinuti, uvijek skinete gornju stavku.

Pokazat ću vam niz poziva na djelu s factorialfunkcijom. factorial(5)zapisano je kao 5! a definirano je ovako: 5! = 5 * 4 * 3 * 2 * 1. Evo rekurzivne funkcije za izračunavanje faktorijela broja:

function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }

Sada da vidimo što će se dogoditi ako pozovete fact(3)Ilustracija ispod pokazuje kako se stog mijenja, redak po redak. Najviši okvir u hrpi govori vam koji poziv facttrenutno pozivate .

Primijetite kako svaki poziv na factima svoju kopiju x. To je vrlo važno za rad rekurzije. Ne možete pristupiti kopiji druge funkcije x.

Jeste li već pronašli ključ?

Vratimo se kratko na izvorni primjer traženja ključa u ugniježđenim okvirima. Zapamtite, prva metoda bila je iterativna pomoću petlji. Tom metodom napravite hrpu kutija za pretragu, tako da uvijek znate koje okvire još trebate pretražiti.

No, u rekurzivnom pristupu nema hrpe. Kako vaš algoritam ipak zna koje okvire još morate izgledati? "Hrpa kutija" sprema se na stog. Ovo je niz napola dovršenih poziva funkcija, svaki sa svojim popolovnim popisom okvira koje treba pregledati. Stog prati gomilu kutija za vas!

A zahvaljujući rekurziji napokon možete pronaći ključ i dobiti košulju!

Također možete pogledati ovaj petominutni video koji sam napravio o rekurziji. Trebao bi ojačati ove koncepte rekurzije.

Zaključak

Nadam se da vam je ovaj članak donio više jasnoće o rekurziji u programiranju. Ovaj se članak temelji na lekciji iz mog novog video tečaja iz Manning Publications pod nazivom Algoritmi u pokretu. Tečaj (a također i ovaj članak) temelji se na nevjerojatnoj knjizi Grokking Algorithms Adita Bhargave. On je taj koji je nacrtao sve zabavne ilustracije u ovom članku.

Ako najbolje učite kroz knjige, nabavite knjigu! Ako najbolje učite putem videozapisa, razmislite o kupnji mog tečaja.

Uštedite 39% na mom tečaju pomoću koda ' 39carnes '!

I na kraju, da biste uistinu razumjeli rekurziju, morate ponovno pročitati ovaj članak. ?