>> [Musiikkia]
>> DOUG Lloyd: Olet luultavasti ajattelevat, että koodi on vain käytetään tehtävän suorittamiseksi.
Voit kirjoittaa sen ulos.
Se tekee jotain.
Se on aika paljon se.
>> Käännät sitä.
Käynnistät ohjelman.
Olet hyvä mennä.
>> Mutta uskokaa tai älkää, jos koodataan pitkään,
te todella voi tulla nähdä koodi jotain, joka on kaunis.
Se ratkaisee ongelman erittäin mielenkiintoinen tapa,
tai siellä on vain jotain todella siisti siitä, miten se näyttää.
Saatat nauraa minua, mutta se on totta.
Ja rekursio on yksi tapa tavallaan saat tämän idean
kaunis, tyylikäs näköisiä koodi.
Se ratkaisee ongelmia tavoilla, ovat mielenkiintoisia, helppo visualisoida,
ja yllättävän lyhyt.
>> Tapa rekursio teokset on, rekursiivinen funktio
määritellään funktio, joka kutsuu itselleen osana sen täytäntöönpanoa.
Tämä saattaa tuntua hieman oudolta, ja näemme hieman
siitä, miten tämä toimii hetki.
Mutta jälleen kerran, nämä rekursiiviset menettelyt ovat
tulee olemaan niin tyylikäs koska he ovat menossa
tämän ongelman ratkaisemiseksi ilman joilla on kaikki nämä muut toiminnot
tai nämä pitkät silmukoita.
Näet että nämä rekursiiviset menettelyt ovat menossa katsomaan niin lyhyt.
Ja he todella aikovat tehdä koodi näyttää paljon kauniimpi.
>> Annan teille esimerkin Tämän miten
rekursiivinen menettely voitaisiin määritellä.
Joten jos olet perehtynyt tähän alkaen matematiikka luokka monta vuotta sitten,
Siinä on jotain kutsutaan kertoma-toiminto, joka on yleensä
merkitty huutomerkki, joka määritellään yli kaikki positiiviset kokonaisluvut.
Ja siten, että n kertoma lasketaan
on kerrot kaikki numerot vähemmän kuin
tai yhtä suuri kuin n-together-- kaikki kokonaisluvut alle
tai yhtä suuri kuin n yhdessä.
>> Joten 5 kertoma on 5 kertaa 4 kertaa 3 kertaa 2 kertaa 1.
Ja 4 kertoma on 4 kertaa 3 kertaa 2 kertaa 1 ja niin edelleen.
Saat ajatus.
>> Kuten ohjelmoijat, emme käyttää n, huutomerkki.
Niin me määritellä factorial toimivat tosiasia n.
Ja käytämme kertoma luoda rekursiivinen ratkaisu ongelmaan.
Ja luulen, että saatat löytää että se on paljon enemmän visuaalisesti
houkutteleva kuin iteratiivinen versio, joka
me myös katsomaan hetkessä.
>> Joten tässä on pari facts-- pun intended--
noin factorial-- kertoma toiminto.
Kertoma 1, kuten sanoin, on 1.
Kertoma 2 on 2 kertaa 1.
Kertoma 3 on 3 kertaa 2 kertaa 1, ja niin edelleen.
Puhuimme 4 ja 5 jo.
>> Mutta katsot tätä, ei ole tämä totta?
Eikö kertoma 2 vain 2 kertaa kertoma 1?
Tarkoitan, kertoma 1 on 1.
Joten miksi emme voi vain sanoa, että, koska kertoma 2 on 2 kertaa 1,
se on oikeastaan ​​vain 2 kertaa kertoma 1?
>> Ja sitten ulottuu että ajatus, ei kertoman 3
vain 3 kertaa kertoma 2?
Ja kertoma 4 on 4 kertaa kertoma 3, ja niin edelleen?
Itse asiassa, kertoma tahansa numero voi vain
ilmaistaan ​​jos sellainen on viedä tätä ulos ikuisesti.
Voimme sellaista yleistää kertoma ongelma
koska se on n kertaa kertoma n miinus 1.
Se on n kertaa tuote kaikki numerot vähemmän kuin minä.
>> Tämä ajatus, tämä yleistys ongelma,
antaa meille mahdollisuuden rekursiivisesti määritellä kertoma toiminnon.
Kun määrittää funktion rekursiivisesti, siellä
kaksi asiaa, jotka täytyy olla osa sitä.
Sinun täytyy olla jotain kutsutaan perustapaus, joka, kun laukaista se,
pysäyttää rekursiivinen prosessi.
>> Muutoin toiminto, joka kutsuu itself-- kuten ehkä imagine--
voisi jatkua ikuisesti.
Funktiokutsut toiminto kehottaa funktiokutsut
funktiokutsuja toiminto.
Jos sinulla ei ole tapa pysäyttää sen, ohjelma
on tehokkaasti jumissa klo päättymättömään silmukkaan.
Se kaatuu lopulta, koska se tulee loppuu muisti.
Mutta se sivuseikka.
>> Meillä on oltava jokin muu tapa lopettaa asioita lisäksi meidän ohjelma kaatuu,
koska ohjelma joka kaatuu on luultavasti ole kaunis tai tyylikäs.
Ja niin me kutsumme tätä perustapaus.
Tämä on yksinkertainen ratkaisu ongelmaan, joka lopettaa
rekursiivinen prosessi syntymisen.
Joten se on yksi osa rekursiivinen funktio.
>> Toinen osa on rekursiivinen tapauksessa.
Ja tämä on silloin rekursio todella tapahtuu.
Tämä on, jos toiminto kutsua itseään.
>> Se ei kutsua itseään täsmälleen samalla tavalla kuin se oli nimeltään.
Se tulee olemaan hieman vaihtelua joka tekee ongelma on
yrittää ratkaista pikkuinen vähän pienempi.
Mutta se yleensä kulkee pukki ratkaista suurin liuoksen
eri puhelun ruodussa.
>> Mikä näistä näyttää kuten pohja tässä tapauksessa?
Kumpi näistä näyttää Yksinkertaisin ratkaisu ongelmaan?
Meillä on nippu factorials, ja voisimme jatkaa
menossa on-- 6, 7, 8, 9, 10, ja niin edelleen.
>> Mutta yksi näistä näyttää hyvä asia olla perustapaus.
Se on hyvin yksinkertainen ratkaisu.
Meidän ei tarvitse tehdä mitään erityistä.
>> Kertoma 1 on vain 1.
Meidän ei tarvitse tehdä mitään kertominen lainkaan.
Tuntuu siltä, ​​jos aiomme yrittää ratkaista tämä ongelma,
ja meidän täytyy pysähtyä rekursio jonnekin,
me luultavasti halua lopettaa se kun pääsemme 1.
Emme halua lopettaa ennen sitä.
>> Joten jos me määritellään meidän kertoma toiminto,
tässä on luuranko varten miten voisimme tehdä.
Meidän on plug näissä kahdessa things-- perusskenaariossa ja rekursiivinen tapaus.
Mikä perustapaus?
Jos n on yhtä kuin 1, palauttaa 1-- se on todella yksinkertainen ongelma ratkaista.
>> Kertoma 1 on 1.
Se ei ole 1 kertaa mitään.
Se on vain 1.
Se on erittäin helppo tosiasia.
Ja jotta voi olla meidän perustapaus.
Jos saamme kulunut 1 tähän toiminto, me vain palata 1.
>> Mikä rekursiivinen tapauksessa luultavasti näyttää?
Jokaista muu numero lisäksi 1, mikä malli?
No, jos viemme kertoma n,
se on n kertaa kertoma n miinus 1.
>> Jos viemme kertoma 3, se on 3 kertaa kertoma 3 miinus 1,
tai 2.
Joten jos emme ole katsomalla 1, muuten
palata n kertaa kertoma n miinus 1.
Se on melko yksinkertainen.
>> Ja vuoksi, joilla on hieman puhtaampi ja tyylikäs koodi,
tietävät, että jos meillä on yksilinjainen silmukoita tai yksilinjainen ehdollisen oksat,
voimme päästä eroon kaikista aaltosulkumerkkien heidän ympärillään.
Joten voimme vahvistaa tätä tähän.
Tämä on täsmälleen sama toiminnot kuin tämä.
>> Olen vain ottamalla pois kihara henkselit, koska siellä on vain yksi rivi
sisäpuolella näiden ehdollisen oksat.
Joten nämä käyttäytyvät identtisesti.
Jos n on yhtä kuin 1, palauttaa 1.
Muutoin palaa n kertaa kertoma n miinus 1.
Joten Teemme ongelma pienempiä.
Jos n alkaa out 5, aiomme palata 5 kertaa kertoma 4.
Ja näemme hetken kun puhumme noin puhelun stack-- toisessa video
jossa puhumme soittaa stack-- me oppia
miksi juuri tämä prosessi toimii.
>> Mutta kun kertoma 5 sanoo palata 5 kertaa kertoma 4, ja 4
aikoo sanoa, OK, hyvin, paluu 4 kertaa kertoma 3.
Ja kuten näette, olemme eräänlainen lähestyy 1.
Saamme lähemmäksi ja lähemmäksi että perustapaus.
>> Ja kun me osuma perustapaus, kaikki aiemmat toiminnot
on vastaus he etsivät.
Kertoma 2 sanoi paluu 2 kertaa kertoma 1.
No, kertoma 1 palauttaa 1.
Joten vaatimus factorial 2 voi palata 2 kertaa 1,
ja antaa ne takaisin faktoria 3, joka odottaa, että tulos.
>> Ja sitten se voi laskea sen seurauksena, 3 kertaa 2 on 6,
ja antaa sen takaisin kertoma 4.
Ja vielä, meillä on video kutsupino
jos tämä on kuvattu hieman enemmän kuin mitä minä sanon nyt.
Mutta tämä on se.
Tämä yksin on ratkaisu laskettaessa kertoman numeron.
>> Se on vain neljä riviä koodia.
Se on aika siistiä, eikö?
Se on tavallaan seksikäs.
>> Niin yleensä, mutta ei aina, rekursiivinen funktio
voi korvata silmukan ei-rekursiivinen funktio.
Joten tässä, vierekkäin, on iteratiivinen versio kertoma toiminnon.
Nämä molemmat laske täsmälleen sama asia.
>> Molemmat laskea kertoma n.
Versio vasemmalla käyttää rekursio tehdä se.
Versio oikealla käyttää iteraation tehdä se.
>> Ja ilmoitus, meidän täytyy julistaa muuttujan kokonaisluku tuotetta.
Ja sitten me silmukka.
Niin kauan kuin n on suurempi kuin 0, me pitää kertomalla että tuotteen n
ja pienentämällä n saakka laskemme tuotetta.
Joten nämä kaksi tehtävää, jälleen, tehdä täsmälleen sama asia.
Mutta he eivät tee sitä täsmälleen samalla tavalla.
>> Nyt, on mahdollista on enemmän kuin yksi emäs
tapauksessa tai useamman kuin yhden rekursiivinen tapauksessa riippuen
siitä, mitä toiminto yrittää tehdä.
Et ole välttämättä rajoitu vain yhden emäksen tapaus tai yhden rekursiivinen
tapauksessa.
Joten esimerkki jotain useita pohja tapauksia
voisi olla this-- Fibonaccin numerosarja.
>> Voit muistamme peruskoulun päivää
että Fibonaccin määritellään kuten this-- ensimmäinen elementti on 0.
Toinen elementti on 1.
Molemmat näistä ovat vain määritelmän.
>> Sitten joka toinen elementti on määritelty summana n miinus 1 ja n miinus 2.
Joten kolmas elementti olisi 0 plus 1 on 1.
Ja sitten neljäs elementti olisi toinen elementti, 1,
plus kolmas elementti, 1.
Ja että olisi 2.
Ja niin edelleen ja niin edelleen.
>> Joten tässä tapauksessa, meillä on kaksi pohja tapausta.
Jos n on yhtä kuin 1, palauttaa 0.
Jos n on 2, paluu 1.
Muuten palauttaa Fibonaccin n miinus 1 plus Fibonaccin n miinus 2.
>> Niin, että useita pohja tapauksissa.
Entä useita rekursiivinen tapauksissa?
No, siinä on jotain nimeltään Collatz Conjecture.
En aio sanoa, tiedät mitä se on,
koska se on todella meidän lopullinen ongelma tässä video.
Ja se on meidän liikunta työskennellä yhdessä.
>> Joten tässä mitä Collatz Conjecture is--
se koskee kaikkia positiivinen kokonaisluku.
Ja se spekuloi, että se on aina mahdollista saada takaisin
1, jos teet nämä toimet.
Jos n on 1, lopeta.
Meillä takaisin 1, jos n on 1.
>> Muuten, läpi tämän prosessin uudelleen n jaettuna 2.
Ja katso jos voit saada takaisin 1.
Muuten, jos n on pariton, läpi Tämän prosessin uudelleen 3n + 1,
tai 3 kertaa N + 1.
Joten tässä meillä on yhden emäksen tapaus.
Jos n on yhtä kuin 1, lopettaa.
Emme tee enää rekursio.
>> Mutta meillä on kaksi rekursiivista tapausta.
Jos n on parillinen, teemme yhden rekursiivinen tapauksessa kutsuen n jaettuna 2.
Jos n on pariton, teemme eri rekursiivinen tapauksessa 3 kertaa n ja 1.
>> Ja niin tavoite tämä video on ottaa toisen, keskeyttää videon,
ja yrittää kirjoittaa tätä rekursiivinen funktio Collatz
jossa voit kulkea arvo n, ja se laskee, kuinka monta askelta se
tekee päästä 1, jos aloitat n ja noudatat niitä vaiheita yläpuolelle.
Jos n on 1, se vie 0 vaiheita.
Muuten, se tulee ottaa yksi askel plus kuitenkin
monta askelta kuluu joko n jaettuna 2, jos n on parillinen tai 3n + 1
jos n on pariton.
>> Nyt, olen laittaa ruudulle täällä pari testi asioita sinulle,
pari testejä tapauksissa sinulle, nähdä mitä nämä eri Collatz numerot ovat,
ja myös kuva vaiheet, jotka
on mennyt läpi niin voit tavallaan nähdä tämän prosessin toiminnassa.
Joten jos n on yhtä suuri kuin 1, Collatz n on 0.
Sinun ei tarvitse tehdä tahansa saadakseen takaisin 1.
Olet jo siellä.
>> Jos n on 2, se kestää yksi askel päästä 1.
Aloitat 2.
Hyvin, 2 ei ole yhtä kuin 1.
Joten se tulee olemaan yksi askel plus kuitenkin monta askelta se
ottaa n jaettuna 2.
>> 2 jaettuna 2 on 1.
Joten se vie yhden askeleen plus kuitenkin monta askelta kuluu 1.
1 ottaa nolla vaiheet.
>> 3, kuten näette, siellä aivan muutaman askeleen mukana.
Menet 3.
Ja sitten menet 10, 5, 16, 8, 4, 2, 1.
Se kestää seitsemän askelta päästä takaisin 1.
Ja kuten näette, siellä Pari muuta testitapaukset täällä
testata ohjelman.
Joten jälleen, keskeyttää videon.
Ja Menen hypätä takaisin nyt mitä todellinen prosessi on täällä,
mitä tämä arveluja on.
>> Katso jos voit selvittää miten määritellä Collatz n
niin, että se laskee, kuinka monta toimiin se tekee päästä 1.
Joten toivottavasti olet keskeytetty video ja et ole vain odottavat minua
antaa sinulle vastauksen täällä.
Mutta jos olet, hyvin, tässä on vastaus muutenkin.
>> Joten tässä on mahdollinen määritelmä ja Collatz funktion.
Meidän perustaa case-- jos n on on 1, palaamme 0.
Se ei ota mitään askeleen päästä takaisin 1.
>> Muuten, meillä on kaksi rekursiivista cases-- yksi parilliset numerot ja yksi outoa.
Tapa I -testissä parillisia on tarkistaa, jos n mod 2 tuloksena 0.
Tämä on periaatteessa, jälleen, kysyvät,
Jos muistatte, mitä mod is-- jos en jakaa n 2 on olemassa mitään jäljellä?
Se olisi parillinen määrä.
>> Ja niin jos n mod 2 tuloksena 0 on testaus on tämä parillinen.
Jos näin on, haluan palata 1, koska tämä on ehdottomasti
ottamalla yksi askel plus Collatz of mikä määrä on puoli minusta.
Muuten, haluan palata 1 plus Collatz 3 kertaa n ja 1.
Joka oli toinen rekursiivinen askel, että me
voisi laskea Collatz-- useita vaiheita
se tekee päästä takaisin 1 annetaan numero.
Joten toivottavasti tämä esimerkki antoi sinulle hieman
of maku rekursiivinen menettelyjä.
Toivottavasti luulet koodi on hieman kaunis toteutuessaan
tyylikäs, rekursiivinen tavalla.
Mutta vaikka ei, rekursiota on todella tehokas työkalu kuitenkin.
Ja niin se on varmasti jotain saada pään ympäri,
koska voit luoda melko viileä ohjelmia recursion
jotka muuten saattaisivat olla monimutkainen kirjoittaa jos käytät silmukoita ja iterointia.
Olen Doug Lloyd.
Tämä on CS50.