Kuinka rekursio toimii - selitetään vuokaavioilla ja videolla

"Rekurssin ymmärtämiseksi on ensin ymmärrettävä rekursio."

Rekursio voi olla vaikea ymmärtää - varsinkin uusille ohjelmoijille. Yksinkertaisimmassa muodossaan rekursiivinen toiminto kutsuu itseään. Saanen yrittää selittää esimerkillä.

Kuvittele, että menet avaamaan makuuhuoneesi oven ja se on lukittu. Kolmivuotias poikasi ponnahtaa nurkan takaa ja ilmoittaa, että hän kätki ainoan avaimen laatikkoon. ("Aivan kuin hän", luulet.) Olet myöhässä töistä ja sinun on todella mentävä huoneeseen saadaksesi paitasi.

Avaat laatikon vain löytääksesi lisää ruutuja. Laatikot laatikoiden sisällä. Ja et tiedä kumpi on avain! Sinun on hankittava tuo paita pian, joten sinun on ajateltava hyvä algoritmi avain löytämiseksi.

Algoritmin luomiseen tälle ongelmalle on kaksi päämenetelmää: iteratiivinen ja rekursiivinen. Tässä ovat molemmat lähestymistavat vuokaavioina:

Mikä lähestymistapa näyttää sinulle helpommalta?

Ensimmäinen lähestymistapa käyttää while-silmukkaa. Vaikka kasa ei ole tyhjä, tartu laatikkoon ja katso se läpi. Tässä on joitain JavaScript-innoittamia pseudokoodeja, jotka osoittavat mitä tapahtuu. (Pseudokoodi on kirjoitettu kuin koodi, mutta sen on tarkoitus olla enemmän kuin ihmisen puhe.)

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

Toinen tapa käyttää rekursiota. Muista, että rekursio on paikka, jossa funktio kutsuu itseään. Tässä on toinen tapa pseudokoodissa.

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

Molemmilla lähestymistavoilla saavutetaan sama asia. Rekursiivisen lähestymistavan pääasiallinen tarkoitus on, että kun ymmärrät sen, sen lukeminen voi olla selkeämpää. Rekursio ei ole oikeastaan ​​mitään hyötyä. Toistuva lähestymistapa silmukoilla voi joskus olla nopeampi. Mutta lähinnä rekursio on yksinkertainen.

Lisäksi, koska monet algoritmit käyttävät rekursiota, on tärkeää ymmärtää, miten se toimii. Jos rekursio ei edelleenkään näytä sinulle yksinkertaiselta, älä huoli: Aion käydä läpi muutama esimerkki.

Perus- ja rekursiivinen tapaus

Rekursiivisen funktion kirjoittaessasi sinun on otettava huomioon ääretön silmukka. Tällöin toiminto kutsuu itseään ... eikä koskaan lopeta itseään!

Voit esimerkiksi kirjoittaa laskutoiminnon. Voit kirjoittaa sen rekursiivisesti JavaScriptiä näin:

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

Tämä toiminto jatkaa laskemista ikuisesti. Jos suoritat vahingossa koodia äärettömällä silmukalla, voit tappaa komentosarjan painamalla "Ctrl-C". (Tai jos joskus käytät CodePeniä kuten minä, sinun on lisättävä URL-osoitteen loppuun "? Turn_off_js = true".)

Rekursiivisen toiminnon on aina sanottava, milloin lopettaa itsensä toistaminen. Rekursiivisessa funktiossa tulisi aina olla kaksi osaa: rekursiivinen tapaus ja peruskotelo. Rekursiivinen tapaus on, kun toiminto kutsuu itseään. Perustapauksena on, kun toiminto lopettaa itsensä kutsun. Tämä estää loputtomia silmukoita.

Tässä on taas lähtölaskenta-toiminto, jossa on perustapaus:

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.

Ei välttämättä ole selvää, mitä tässä toiminnossa tapahtuu. Käyn läpi mitä tapahtuu, kun soitat lähtölaskenta-funktiolle "5".

Aloitetaan tulostamalla numero 5 käyttämällä console.log. Koska viisi ei ole pienempi tai yhtä suuri kuin nolla, siirrymme toiseen lauseeseen. Kutsumme siellä lähtölaskentafunktiota uudelleen numerolla neljä (5–1 = 4?).

Kirjaamme numeron 4. Jälleen, iei ole pienempi tai yhtä suuri kuin nolla, joten siirrymme toiseen lausekkeeseen ja soitamme lähtölaskennan luvulla 3. Tämä jatkuu kunnesion nolla. Kun näin tapahtuu, me log numero nolla, ja sitten ion pienempi kuin tai yhtä suuri kuin nolla. Lopulta pääsemme palautuslausekkeeseen ja ponnahdamme pois toiminnosta.

Puhelupino

Rekursiivisissa toiminnoissa käytetään niin sanottua puhelupinoa. Kun ohjelma kutsuu toiminnon, se menee puhelupinon päälle. Tämä on samanlainen kuin pino kirjoja. Voit lisätä asioita yksi kerrallaan. Sitten, kun olet valmis ottamaan jotain pois, otat aina pois päällimmäisen tuotteen.

Näytän sinulle puhelun pinon factorialtoiminnassa. factorial(5)on kirjoitettu 5: ksi! ja se määritellään seuraavasti: 5! = 5 * 4 * 3 * 2 * 1. Tässä on rekursiivinen funktio, jolla lasketaan luvun kerroin:

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

Katsotaanpa nyt, mitä tapahtuu, jos soitat fact(3). Kuvassa näkyy, kuinka pino muuttuu rivi riviltä. Pinon ylin ruutu kertoo, mihin puheluun factolet parhaillaan.

Huomaa, kuinka jokaisella puhelulla facton oma kopio x. Tämä on erittäin tärkeää, jotta rekursio toimii. Et voi käyttää toisen toiminnon kopiota x.

Löysitkö avaimen jo?

Palataan lyhyesti takaisin alkuperäiseen esimerkkiin avaimen etsimisestä sisäkkäisistä laatikoista. Muista, että ensimmäinen menetelmä oli iteratiivinen käyttäen silmukoita. Tällä menetelmällä teet kasan laatikoita etsimiseen, joten tiedät aina, mitkä laatikot sinun on vielä etsittävä.

Rekursiivisessa lähestymistavassa ei kuitenkaan ole kasaa. Mistä algoritmisi tietää, mitkä laatikot sinun on silti näytettävä? ”Pino of box” tallennetaan pinoon. Tämä on pino puoliksi valmistuneita toimintokutsuja, joilla kullakin on oma puolitietoinen luettelo laatikoista, joita voit tarkastella. Pino seuraa kirjaa kasa-annoksesta puolestasi!

Rekursioiden ansiosta voit vihdoin löytää avaimen ja saada paitasi!

Voit myös katsoa tämän 5 minuutin videon, jonka tein rekursiosta. Sen pitäisi vahvistaa näitä rekursiokäsitteitä.

Johtopäätös

Toivon, että tämä artikkeli toi sinulle enemmän selkeyttä ohjelmoinnin rekursiosta. Tämä artikkeli perustuu uuden videokurssin opetukseen Manning Publications -ohjelmassa nimeltä Algorithms in Motion. Kurssi (ja myös tämä artikkeli) perustuu Adit Bhargavan hämmästyttävään kirjaan Grokking Algorithms. Hän piirsi kaikki tämän artikkelin hauskat kuvitukset.

Jos opit parhaiten kirjojen kautta, hanki kirja! Jos opit parhaiten videoiden kautta, harkitse kurssini ostamista.

Hanki 39% kurssiltani koodilla 39carnes !

Ja lopuksi, jotta voisit todella ymmärtää rekursiota, sinun on luettava tämä artikkeli uudelleen. ?