Kaip vyksta rekursija - paaiškinta schemomis ir vaizdo įrašu

„Norint suprasti rekursiją, pirmiausia reikia suprasti rekursiją.“

Rekursiją gali būti sunku suprasti - ypač naujiems programuotojams. Paprasčiausia forma rekursinė funkcija yra ta, kuri save vadina. Leiskite pabandyti paaiškinti pavyzdžiu.

Įsivaizduokite, kad einate atidaryti savo miegamojo durų ir jos užrakintos. Tavo trejų metų sūnus užlipa iš už kampo ir praneš, kad jis dėžutėje paslėpė vienintelį raktą. („Kaip ir jis“, jūs manote.) Jūs vėluojate į darbą ir jums tikrai reikia užeiti į kambarį, kad gautumėte marškinius.

Dėžutę atidarote tik norėdami rasti ... daugiau langelių. Dėžutės dėžėse. Ir jūs nežinote, kuris turi raktą! Tuos marškinėlius turi įsigyti netrukus, todėl turi sugalvoti gerą algoritmą, kaip surasti tą raktą.

Yra du pagrindiniai būdai, kaip sukurti šios problemos algoritmą: iteracinis ir rekursinis. Čia pateikiami abu būdai kaip schemos:

Kuris požiūris jums atrodo lengvesnis?

Pirmasis požiūris naudoja „while loop“. Kol krūva nėra tuščia, griebk dėžę ir žiūrėk pro ją. Štai keletas „JavaScript“ įkvėptų pseudokodų, rodančių, kas vyksta. (Pseudokodas yra parašytas kaip kodas, bet labiau panašus į žmogaus kalbą.)

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!") } } }}

Antruoju būdu naudojamas rekursija. Atminkite, kad rekursija yra vieta, kur funkcija save vadina. Čia yra antrasis pseudokodo būdas.

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!") } } }

Abiem būdais pasiekiamas tas pats dalykas. Pagrindinis rekursinio metodo naudojimo tikslas yra tai, kad jį supratus, gali būti aiškiau skaityti. Rekursijos naudojimas iš tikrųjų nėra naudingas. Kartotinis metodas su kilpomis kartais gali būti greitesnis. Tačiau dažniausiai pirmenybė teikiama rekurso paprastumui.

Be to, kadangi daugelyje algoritmų naudojama rekursija, svarbu suprasti, kaip tai veikia. Jei rekursija jums vis tiek neatrodo paprasta, nesijaudinkite: apžvelgsiu dar kelis pavyzdžius.

Bazinis ir rekursinis atvejis

Kažkas, į ką turite atkreipti dėmesį, rašydami rekursinę funkciją, yra begalinė kilpa. Tai yra tada, kai funkcija nuolat vadina save ... ir niekada nenustoja skambinti pati!

Pavyzdžiui, galbūt norėsite parašyti skaičiavimo funkciją. Tai galite parašyti rekursyviai „JavaScript“ taip:

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

Ši funkcija bus amžinai skaičiuojama. Jei netyčia paleidote kodą su begaline kilpa, galite paspausti „Ctrl-C“, kad užmuštumėte scenarijų. (Arba, jei kartais naudojate „CodePen“ kaip aš, prie URL pabaigos turite pridėti „? Turn_off_js = true“.)

Rekursinė funkcija visada turi pasakyti, kada nustoti kartotis. Rekursizinei funkcijai visada turėtų būti dvi dalys: rekursinis ir pagrindinis atvejis. Rekurzinis atvejis yra tada, kai funkcija paskambina pati. Pagrindinis atvejis yra tada, kai funkcija nustoja skambinti pati. Tai apsaugo nuo begalinių kilpų.

Čia yra vėl skaičiavimo funkcija su pagrindiniu atveju:

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.

Gali būti neaišku, kas tiksliai vyksta šioje funkcijoje. Peržiūrėsiu, kas atsitinka, kai paskambinsite atgalinės atskaitos funkcijai, einančiai „5“.

Pradedame spausdindami skaičių 5 naudodami console.log. Kadangi penki nėra mažesni arba lygūs nuliui, einame prie kito teiginio. Čia mes vėl vadiname skaičiavimo funkciją skaičiumi keturi (5–1 = 4?).

Mes užregistruojame skaičių 4. Vėlgi, iyra ne mažesnis nei lygus nuliui, todėl einame prie kito sakinio ir skambiname atgaliniu skaičiumi su 3. Tai tęsiasi ikiilygus nuliui. Kai taip atsitiks, mes užregistruosime skaičių nulis ir tada ibus mažesnis arba lygus nuliui. Pagaliau mes prieiname prie grįžimo sakinio ir iššokame iš funkcijos.

Skambučių krūva

Rekursinės funkcijos naudoja vadinamąjį „skambučių kaminą“. Kai programa iškviečia funkciją, ši funkcija patenka į skambučių kamino viršų. Tai panašu į knygų šūsnį. Pridedate dalykų po vieną. Tada, kai esate pasirengęs ką nors nusimesti, visada nuimkite viršutinį daiktą.

Aš jums parodysiu skambučių kaminą veikiant su factorialfunkcija. factorial(5)parašyta kaip 5! ir jis apibrėžiamas taip: 5! = 5 * 4 * 3 * 2 * 1. Čia pateikiama rekursinė funkcija skaičiaus faktorialui apskaičiuoti:

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

Dabar pažiūrėkime, kas atsitiks, jei paskambinsite fact(3). Paveikslėlyje parodyta, kaip keičiasi kaminas, eilutė po eilutės. Viršutiniame rietuvės langelyje nurodoma, kokį skambutį factšiuo metu atliekate.

Atkreipkite dėmesį, kaip kiekvienas skambutis factturi savo kopiją x. Tai labai svarbu, kad rekursija veiktų. Negalite pasiekti kitos funkcijos kopijos x.

Ar jau radai raktą?

Trumpai grįžkime prie pirminio pavyzdžio apie raktų paiešką įdėtose dėžutėse. Atminkite, kad pirmasis metodas buvo kartotinis, naudojant kilpas. Taikydami šį metodą, jūs padarote krūvelę dėžių, kad galėtumėte ieškoti, kad visada žinotumėte, kokių langelių vis dar reikia ieškoti.

Tačiau rekursiškame požiūrie nėra krūvos. Kaip jūsų algoritmas žino, kurios dėžutės vis dėlto turite atrodyti? „Dėželių krūva“ išsaugoma ant kamino. Tai yra pusiau užbaigtų funkcijų iškvietimų krūva, kiekviena iš jų turi savo pusiau išsamų langelių, kuriuos reikia peržiūrėti, sąrašą. Šūsnis seka dėžių krūvą už jus!

Rekursijos dėka jūs pagaliau galite rasti raktą ir gauti savo marškinius!

Taip pat galite žiūrėti šį mano sukurtą 5 minučių vaizdo įrašą apie rekursiją. Tai turėtų sustiprinti šias rekursijos koncepcijas.

Išvada

Tikiuosi, kad šis straipsnis jums suteikė daugiau aiškumo apie programavimo rekursiją. Šis straipsnis yra paremtas mano naujo vaizdo įrašų kurso „Mananning Publications“ pamoka „Algoritmai judesyje“. Kursas (ir šis straipsnis) yra pagrįstas nuostabia Adit Bhargava knyga „Grokking Algorithms“. Jis yra tas, kuris nupiešė visas linksmas iliustracijas šiame straipsnyje.

Jei geriausiai mokotės iš knygų, gaukite knygą! Jei geriausiai mokotės per vaizdo įrašus, apsvarstykite galimybę įsigyti mano kursą.

Gaukite 39% nuolaidą mano kursui naudodami kodą „ 39carnes “!

Galiausiai, norėdami iš tikrųjų suprasti rekursiją, turite perskaityti šį straipsnį dar kartą. ?