>> ZAMYLA: Jotta ymmärtäisimme rekursio, sinun on
ensin ymmärtää rekursio.
Ottaa rekursio ohjelmien suunnitteluun keinoin että sinulla on itseensä viittaavan
määritelmiä.
Rekursiivinen tietorakenteita, esimerkiksi ovat tietorakenteita, jotka
sisältyvät itse niiden määritelmät.
Mutta tänään, aiomme keskittyä rekursiiviseen toimintoja.
>> Muista, että funktiot tuloa, argumentteja, ja palauttaa arvon niiden
tuotos edustaa Tämä kaavio täällä.
Keksimme laatikon ruumis toiminto, joka sisältää joukon
ohjeet, jotka tulkitsevat tulo ja antaa lähdön.
Tarkastella lähemmin kehossa toiminnon voi paljastaa puhelut
myös muita toimintoja.
Ota tämä yksinkertainen tehtävä, foo, että ottaa yhden merkkijonon tulo-ja
tulostaa kuinka monta kirjettä että merkkijono on.
Toiminto strlen, jousikvartetille pituus, kutsutaan, joiden tuotanto on
tarvitaan puhelun printf.
>> Nyt, mitä tekee rekursiivinen funktio erityisen se, että se kutsuu itseään.
Voimme edustaa tämän rekursiivinen soittaa tällä oranssi nuoli
silmukoiden takaisin itselleen.
Mutta täytäntöönpanosta itse uudestaan ​​vain tee uusi rekursiokutsu, ja
toinen ja toinen.
Mutta rekursiivinen toiminnot ei voi olla ääretön.
Heidän täytyy lopettaa jotenkin, tai Ohjelmaa toteutetaan ikuisesti.
>> Joten meidän täytyy löytää keino murtaa ulos rekursiokutsua.
Kutsumme tätä perustapaus.
Kun pohja tapauksessa ehto täyttyy, funktio palauttaa tekemättä
toinen rekursiokutsu.
Ota tämä toiminto, hi, void funktio joka vie int n syötteenä.
Perustapauksessa tulee ensin.
Jos n on pienempi kuin nolla, tulosta bye ja palata Kaikissa muissa tapauksissa
toiminto tulostaa hi ja toteuttaa rekursiokutsu.
Toinen puhelu toiminto hi kanssa pienennetään syötetty arvo.
>> Nyt, vaikka me painamme hi, toiminto ei lopeta ennen kuin olemme
palauttaa sen paluuarvon tyyppi, tässä tapauksessa mitätön.
Joten jokaisella n muiden kuin perusversion, Tämän toiminnon hi palaa hi
n: n miinus 1.
Koska tämä toiminto on mitätön, vaikka me ei nimenomaisesti kirjoita palata tänne.
Me vain suorittaa toiminnon.
Joten soittaa hi (3) tulostaa hi ja suorita hi (2), joka toteuttaa hi (1) yksi
joka toteuttaa hi (0), jossa Perustapauksessa ehto täyttyy.
Joten hi (0) tulostaa bye ja palaa.
>> OK.
Joten nyt ymmärrämme perusasiat rekursiivinen toiminnot, että he tarvitsevat
vähintään yhden emäksen tapauksessa sekä rekursiokutsu, nyt siirtyä
mielekkäämmäksi esimerkki.
Joka ei vain palaa mitätöidä mitä tahansa.
>> Katsotaanpa katsomaan factorial toimintaa käytetään yleisimmin
todennäköisyys laskelmat.
Kertoma n on tuote, joka pienempi positiivinen kokonaisluku
ja suuruudeltaan n.
Joten kertoma viisi on 5 kertaa 4 kertaa 3 kertaa 2 kertaa 1, jolloin saatiin 120.
Neljä kertoma on 4 kertaa 3 kertaa 2 kertaa 1 antaa 24.
Ja sama sääntö pätee Minkä tahansa positiivinen kokonaisluku.
>> Joten miten me saatamme kirjoittaa rekursiivinen joka laskee kertoman
Useiden?
No, meidän täytyy tunnistaa sekä perustapauksen ja rekursiokutsu.
Rekursiokutsu on sama kaikissa tapauksissa paitsi pohja
tapauksessa, mikä tarkoittaa, että meidän täytyy löytää malli, joka antaa meille
halutun tuloksen.
>> Tästä esimerkiksi tarkistaa, kuinka 5 kertoma liittyy kertomalla 4 3 2 1
Ja jo samana kertominen löytyy täältä,
määritelmä 4 kertoma.
Näemme siis, että 5 kertoma on vain 5 kertaa 4 kertoma.
Nyt tämä malli sovelletaan 4 kertoma samoin?
Kyllä.
Näemme, että 4 kertoma sisältää kertomalla 3 kertaa 2 kertaa 1,
Aivan sama määritelmä kuin 3 kertoma.
Joten 4 kertoma on yhtä kuin 4 kertaa 3 kertoma, ja niin edelleen ja niin edelleen meidän
kuvio tikkuja kunnes 1 kertoma, joka määritelmän on yhtä suuri kuin 1.
>> Ei ole muita myönteisiä kokonaislukuja vasemmalle.
Joten meillä on malli meidän rekursiokutsu.
n kertoma on yhtä kuin n kertaa kertoma n miinus 1.
Ja meidän tukikohta tapauksessa?
Että olette vain meidän määritelmä 1 kertoma.
>> Joten nyt voimme siirtyä kirjallisesti funktion koodin.
Peruskoron tapauksessa meillä on ehto n on on 1, jos
palaamme 1.
Sitten siirryn rekursiokutsu, palaamme n kertaa
kertoma n miinus 1.
>> Nyt testata tätä meidän.
Kokeillaan kertoma 4.
Per meidän tehtävämme on yhtä 4 kertaa factorial (3).
Kertoma (3) on yhtä suuri kuin 3 kertaa kertoma (2).
Kertoma (2) on yhtä kuin 2 kertaa kertoma (1), joka palauttaa 1.
Kertoma (2) nyt palauttaa 2 kertaa 1, 2.
Kertoma (3) voidaan nyt palata 3 kertaa 2, 6.
Ja lopuksi, kertoma (4) palauttaa 4 kertaa 6, 24.
>> Jos olet kohtaaminen vaikeuksia kanssa rekursiokutsu, teeskennellä, että
toiminto toimii jo.
Mitä tarkoitan tällä, että sinun pitäisi luota rekursiokutsua palata
oikeita arvoja.
Esimerkiksi, jos tiedän, että kertoma (5) on yhtä kuin 5 kertaa
kertoma (4), aion luottaa siihen, että kertoma (4) antaa minulle 24.
Ajattele sitä muuttuja, jos on, kuten jos olet jo määritelty
kertoma (4).
Joten mistään kertoma (n), se on tuote n ja
edellinen kertoma.
Ja tämä edellinen kertoma saadaan soittamalla
kertoma n miinus 1.
>> Nyt, katso jos voit toteuttaa rekursiivinen funktio itse.
Kuormitus terminaalin tai run.cs50.net, ja kirjoittaa funktio summa
joka vie kokonaisluku n ja palauttaa summa peräkkäistä positiivista
kokonaisluvut n 1.
Olen kirjoittanut ulos summia joidenkin arvot auttaa sinua meidän.
Ensinnäkin selvittää perustapauksen kunnossa.
Sitten, katso summa (5).
Voitko ilmaisevat sen toisen summa?
Nyt, entä summa (4)?
Miten voit ilmaista summan (4) toisen suhteen summa?
>> Kun olet summa (5) ja summa (4) ilmaistuna muut summat, katso
jos voit tunnistaa malli summa (n).
Jos ei, kokeile muutamia muita numeroita ja ilmaista summia
toisen suhteen numeroita.
Tunnistamalla kaavoja diskreetti numerot, olet hyvin teidän tapa
tunnistaa malli tahansa n.
>> Rekursio on todella tehokas työkalu, niin tietysti se ei rajoitu
matemaattisia funktioita.
Rekursio voidaan käyttää hyvin tehokkaasti käsitellessään puita esimerkiksi.
Tutustu lyhyttä puita perusteellisempi tarkastelu, mutta nyt
Muistutan, että binäärihaku puita, vuonna Erityisesti koostuvat solmuja, kukin
joiden arvo ja kaksi solmun viitteitä.
Yleensä tämä edustaa isäsolmuun ottaa yksi rivi osoittaa
vasemmalle lapsisolmuun ja yksi oikealle lapsisolmuun.
Rakenne binäärihaku puu soveltuu hyvin
to rekursiivinen haku.
Rekursiokutsu joko kulkee vasemmalle tai oikealle solmu, mutta enemmän
Kyseisen puussa lyhyt.
>> Sano haluat suorittaa toimintansa jokainen solmu binääripuun.
Miten voi mennä siitä?
No, voisit kirjoittaa rekursiivinen toiminto, joka suorittaa operaation
vanhemman solmun ja tekee rekursiivinen soittaa sama tehtävä,
kulkee vasemmalle ja oikea lapsi solmut.
Esimerkiksi tämä toiminto, foo, että Arvo vaihtuu tietyn solmun ja
kaikki sen lapset 1.
Base kyseessä null solmun syitä funktio palauttaa, mikä osoittaa,
että ei ole mitään solmuja jäljellä, että sub-tree.
>> Katsotaanpa kulkea läpi.
Ensimmäinen vanhempi on 13.
Muutamme arvoksi 1 ja soita meidän tehtävämme vasemmalla samoin
kuin oikea.
Toiminto, foo, kutsutaan vasemmalla sub-tree ensin, niin vasen solmu
tulee määrittää uudelleen 1 ja foo voidaan kutsua että solmun lapset,
ensin vasemmalle ja sitten oikealle, ja niin edelleen ja niin edelleen.
Ja kertoa heille, että oksat eivät ole enempää lapsia niin sama prosessi
jatkuu oikealle lapsille kunnes koko puun solmut ovat
virkamieskierrossa 1.
>> Kuten näette, et ole rajoitettu vain yksi rekursiokutsu.
Yhtä monta kuin saavat työnsä tehtyä.
Mitä jos sinulla olisi puu, jossa kukin solmu oli kolme lasta,
Vasen, keskimmäinen ja oikea?
Miten muokkaat foo?
No, yksinkertainen.
Vain lisätä toisen rekursiokutsu ja kulkea keskellä solmu osoitin.
>> Rekursio on hyvin voimakas eikä mainitse elegantti, mutta se voi olla
vaikea käsite aluksi, joten potilaaseen ja vie aikaa.
Aloita perustapaus.
Se on yleensä helpoin tunnistaa, ja sitten voit työskennellä
taaksepäin sieltä.
Tiedät mitä tarvitset saavuttaaksesi base tapauksessa, niin että voima
antaa sinulle muutamia vinkkejä.
Yritä ilmaista erityistapaus kannalta muissa tapauksissa, tai osa-sarjaa.
>> Kiitos katsomassa tämä lyhyt.
Ainakin, nyt voit ymmärtää vitsejä kuten tämä.
Nimeni on Zamyla, ja tämä on CS50.
>> Ota tämä toiminto, hi, void funktio, joka ottaa
int, n, syötteenä.
Perustapauksessa tulee ensin.
Jos n on pienempi kuin 0, tulosta "Hei" ja palata.