Kuidas rekursioon töötab - seda on selgitatud vooskeemide ja videoga

"Rekursiooni mõistmiseks peate kõigepealt aru saama rekursioonist."

Rekursioonist võib olla raske aru saada - eriti uute programmeerijate jaoks. Kõige lihtsamal kujul on rekursiivne funktsioon see, mis kutsub ennast. Lubage mul proovida seletada ühe näitega.

Kujutage ette, et lähete oma magamistoa ust avama ja see on lukus. Teie kolmeaastane poeg hüppab nurga tagant sisse ja annab teada, et peitis ainsa võtme kasti. ("Täpselt nagu tema," arvate teie.) Jätate tööle hiljaks ja peate oma särgi saamiseks tõepoolest tuppa minema.

Avate kasti ainult selleks, et leida ... rohkem kaste. Kastid kastide sees. Ja te ei tea, kummal on võti! Peate selle särgi varsti hankima, nii et peate selle võtme leidmiseks mõtlema hea algoritmi.

Selle probleemi algoritmi loomiseks on kaks peamist lähenemist: iteratiivne ja rekursiivne. Siin on mõlemad lähenemised vooskeemidena:

Milline lähenemine tundub teile lihtsam?

Esimene lähenemine kasutab mõnda aega. Kuigi hunnik pole tühi, haarake karp ja vaadake seda läbi. Siin on mõni JavaScripti inspireeritud pseudokood, mis näitab, mis toimub. (Pseudokood on kirjutatud nagu kood, kuid mõeldud pigem inimese kõne sarnaseks.)

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

Teisel viisil kasutatakse rekursiooni. Pidage meeles, et rekursioon on koht, kus funktsioon ennast kutsub. See on pseudokoodi teine ​​viis.

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

Mõlemad lähenemised saavutavad sama asja. Rekursiivse lähenemisviisi kasutamise peamine eesmärk on see, et kui sellest aru saate, on selle lugemine selgem. Rekursiooni kasutamisest pole tegelikult mingit kasu. Korduv lähenemine koos silmustega võib mõnikord olla kiirem. Kuid peamiselt eelistatakse mõnikord rekursiooni lihtsust.

Kuna paljud algoritmid kasutavad rekursiooni, on oluline mõista selle toimimist. Kui rekursioon ei tundu teile endiselt lihtne, siis ärge muretsege: lähen läbi veel mõned näited.

Baasjuhtum ja rekursiivjuhtum

Miski, mida peate rekursiivse funktsiooni kirjutamisel tähelepanu pöörama, on lõpmatu silmus. See on siis, kui funktsioon kutsub ennast pidevalt ... ja ei lakka kunagi ise helistamast!

Näiteks võite kirjutada ülesarvamise funktsiooni. Võite selle rekursiivselt JavaScripti kirjutada järgmiselt:

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

See funktsioon loendab igavesti. Kui käivitate kogemata koodi lõpmatu silmusega, võite oma skripti tapmiseks vajutada klahvi Ctrl-C. (Või kui te mõnikord kasutate CodePeni nagu mina, peate URL-i lõppu lisama "? Turn_off_js = true".)

Rekursiivne funktsioon peab alati ütlema, millal lõpetada enda kordamine. Rekursiivfunktsioonil peaks alati olema kaks osa: rekursiivjuhtum ja baasjuhtum. Rekursiivne juhtum on see, kui funktsioon kutsub ennast. Põhijuhtum on see, kui funktsioon lõpetab enda helistamise. See hoiab ära lõpmatud silmused.

Siin on uuesti loendamisfunktsioon koos juhtumiga:

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.

See, mis täpselt selles funktsioonis toimub, ei pruugi olla ilmne. Vaatan läbi, mis juhtub, kui helistate loenduri funktsioonile, mis läbib numbri “5”.

Alustame numbri 5 printimisega console.log. Kuna viis pole väiksem või võrdne nulliga, läheme teise lause juurde. Seal kutsume loendefunktsiooni uuesti numbriga neli (5–1 = 4?).

Logime numbri 4. Jällegi, see iei ole väiksem kui null või võrdne, nii et läheme teise lause juurde ja helistame loendiga 3. See jätkub kuniivõrdub nulliga. Kui see juhtub, me sisse number null ja seejärel ion väiksem või võrdne nulliga. Lõpuks jõuame return-avalduseni ja hüppame funktsioonist välja.

Kõnepakk

Rekursiivsed funktsioonid kasutavad nn kõnekogumit. Kui programm kutsub funktsiooni, läheb see funktsioon kõnepinu kohale. See sarnaneb virnaga raamatuid. Lisate asju ükshaaval. Siis, kui olete valmis midagi maha võtma, võtate alati ülemise eseme maha.

Näitan teile factorialfunktsiooni funktsiooniga kõne virna . factorial(5)on kirjutatud kui 5! ja see on määratletud järgmiselt: 5! = 5 * 4 * 3 * 2 * 1. Siin on rekursiivne funktsioon arvu faktori arvutamiseks:

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

Vaatame nüüd, mis juhtub, kui helistate fact(3). Joonis näitab, kuidas virn muutub rea kaupa. Virna ülemine kast näitab teile, millist kõnet factte praegu kasutate.

Pange tähele, kuidas igal kõnel facton oma eksemplar x. See on rekursiooni toimimiseks väga oluline. Te ei pääse juurde mõne muu funktsiooni koopiale x.

Kas leidsite võtme juba üles?

Naaseme lühidalt algse näite juurde pesa kastidest võtme otsimise kohta. Pidage meeles, et esimene meetod oli korduv, kasutades silmusid. Selle meetodi abil valmistate otsimiseks hunniku kaste, nii et teate alati, milliseid kaste peate ikkagi otsima.

Kuid rekursiivses käsitluses pole kuhja. Kuidas saab teie algoritm teada, millised lahtrid peate ikkagi vaatama? “Karpide hunnik” salvestatakse virna. See on virn poolenisti lõpule viidud funktsioonikõnedest, millest igaühel on oma poolik täielik loend kastidest, mida vaadata. Virn jälgib teie jaoks kastikuhja!

Ja tänu rekursioonile leiate lõpuks võtme ja saate oma särgi!

Võite vaadata ka seda minu tehtud 5-minutilist videot rekursiooni kohta. See peaks neid rekursi kontseptsioone tugevdama.

Järeldus

Loodan, et see artikkel tõi teile rohkem selgust rekursiooni kohta programmeerimisel. See artikkel põhineb minu uue videokursuse õppetunnil Manning Publicationsilt Algorithms in Motion. Kursus (ja ka see artikkel) põhineb Adit Bhargava hämmastaval raamatul Grokking Algorithms. Tema joonistas kõik selle artikli lõbusad illustratsioonid.

Kui õpite raamatute kaudu kõige paremini, hankige raamat! Kui õpite videote kaudu kõige paremini, kaaluge minu kursuse ostmist.

Saa 39% soodsamalt minu kursuselt, kasutades koodi 39carnes !

Ja lõpuks, et rekursioonist tõeliselt aru saada, peate selle artikli uuesti läbi lugema. ?