>> [Muzikos grojimo]
>> Doug LLOYD: Jūs tikriausiai manote, kad kodas tik naudojamas atlikti užduotį.
Jūs rašote jį.
Ji kažką.
Tai gana daug.
>> Jūs kaupia ją.
Paleidus programą.
Jūs esate gera eiti.
>> Bet tiki jis ar ne, jei Jūs kodas ilgą laiką,
jūs iš tikrųjų gali ateiti pamatyti kodas, kaip kažkas, kad yra graži.
Tai išsprendžia problemą į labai įdomus būdas,
ar ten tiesiog kažkas tikrai tvarkingas apie tai, kaip jis atrodo.
Jums gali būti juokiasi ne man, bet tai tiesa.
Ir rekursija yra vienas iš būdų rūšiuoti gauti šią idėją
iš gražus, elegantiškas atrodančius kodą.
Tai išsprendžia problemas tokiu būdu, kad yra įdomus, lengva įsivaizduoti,
ir stebėtinai trumpas.
>> Beje Rekursija darbai yra, grįžtamojo funkcija
yra apibrėžiamas kaip funkcija, kad reikalauja pati kaip jos vykdymo.
Tai gali atrodyti šiek tiek keista, ir mes pamatyti šiek tiek
apie, kaip tai veikia iškart.
Bet vėl, tai Rekurentiniai procedūros
bus tokia elegantiška nes jie ketina
išspręsti šią problemą, be turintys visas šias ir kitas funkcijas
ar šie ilgi kilpas.
Pamatysite, kad tai rekursywny procedūros ketiname ieškoti toks trumpas.
Ir jie tikrai ketina padaryti Jūsų kodas atrodo daug gražesnė.
>> Aš duosiu jums pavyzdį tai pamatyti, kaip
rekursywny procedūra gali būti nustatyta.
Taigi, jei esate susipažinę su šiuo iš matematikos klasės, prieš daugelį metų,
Yra kažkas, vadinamas faktorialinis funkcija, kuri paprastai
žymimas kaip šauktukas, kuris yra apibrėžiamas per visi teigiami sveikieji skaičiai.
Ir taip, kad n faktorialas yra apskaičiuojamas
yra padauginti visus numeriai mažiau nei
arba lygus n together-- visi sveikieji mažiau nei
arba lygus n kartu.
>> Taigi 5 faktorialas yra 5 kartus 4 kartus 3 kartus 2 kartus 1.
Ir 4 faktorialas yra 4 kartus 3 kartus 2 kartus 1 ir pan.
Jūs gaunate idėja.
>> Kaip programuotojai, mes do not naudoti N, šauktukas.
Taigi mes apibrėžti faktorialas funkcija taip sakant n.
Ir mes naudosime faktorialas sukurti rekursywny sprendimas problema.
Ir manau, kad jūs galite rasti kad tai daug labiau vizualiai
patrauklus nei kartotinis versija tai, kuris
mes taip pat pažvelgti į šiuo metu.
>> Taigi čia yra pora facts-- kalambūras intended--
apie factorial-- faktorialas funkcija.
1 faktorialas, kaip sakiau, yra 1.
2 faktorialas yra 2 kartus 1.
3 faktorialas yra 3 kartų 2 kartus 1, ir taip toliau.
Mes kalbėjome apie 4 ir 5 jau.
>> Bet žiūri šį, nėra tai tiesa?
Ar ne faktorialas 2 tik 2 kartus 1 faktorialas?
Aš turiu galvoje, 1 faktorialas yra 1.
Taigi kodėl mes negalime tiesiog pasakyti, kad nuo faktorialas 2 yra 2 kartus 1
tai tikrai tik 2 kartus 1 faktorialas?
>> Ir tada išplėsti šią idėją, nėra 3 faktorialas
tik 3 kartus 2 faktorialas?
Ir iš 4 faktorialas yra 4 kartus 3, ir taip toliau faktorialas?
Tiesą sakant, faktorinė bet skaičius gali tik
būti išreikštas jei mes natūra perkėlimų tai iš amžinai.
Mes galime rūšies apibendrinti Faktorialaus problema
kaip tai n kartų faktorialas n minus 1.
Tai n kartų iš produkto visi numeriai mažiau nei mane.
>> Ši idėja, ši apibendrinimas problemos,
leidžia mums rekursyviai apibrėžti faktorialas funkciją.
Kai apibrėžti funkciją rekursyviai, ten
du dalykai, kurie turi būti jos dalimi.
Jums reikia turėti kažką vadinama bazinį scenarijų, kuris, kai jūs sukelti ją,
nustos rekursinį procesą.
>> Priešingu atveju, funkcija, kuri ragina itself-- kaip galima imagine--
gali tęstis amžinai.
Funkcija ragina funkciją vadina funkcija skambučius
funkcija iškviečia funkciją.
Jei jūs neturite būdas jį sustabdyti, savo programą
bus veiksmingai įstrigo ne begalinis ciklas.
Tai bus katastrofos, galų gale, nes jis bus paleisti iš atminties.
Bet tai šalia taško.
>> Mums reikia turėti kokį nors kitą būdą, kaip sustabdyti dalykų Be mūsų programos kritimo,
nes programa, kuri avarijos yra tikriausiai ne gražus ar elegantiška.
Ir taip mes vadiname tai bazinį scenarijų.
Tai yra paprastas sprendimas į problemą, kuri nutraukia
grįžtamojo proceso pasikartojimui.
Taigi, kad viena dalis rekursywny funkcija.
>> Antroji dalis yra grįžtamojo atveju.
Ir tai yra, kai rekursinio bus iš tikrųjų vyksta.
Tai yra, kur funkcija skambinti pati.
>> Jis nebus skambinti pati tiksliai tas pats, kaip jis buvo vadinamas.
Jis bus šiek tiek variacijos kad daro problemą, tai
bando išspręsti smulkutis šiek tiek mažesnis.
Bet tai paprastai praeina spardytis išspręsti tirpalo urmu
į kitą skambutį žemyn linija.
>> Kuris iš šių išvaizda kaip bazine čia?
Kuris iš šių atrodo kaip Paprasčiausias sprendimas yra problema?
Mes turime Factorial krūva, ir galėtume toliau
vyksta on-- 6, 7, 8, 9, 10 ir pan.
>> Tačiau vienas iš šių išvaizda geras pavyzdys būtų bazinį scenarijų.
Tai labai paprastas sprendimas.
Neturime nieko ypatingo.
>> 1 faktorialas yra tik 1.
Neturime daryti bet daugyba ne visiems.
Atrodo, kad jei mes ketiname pabandyti ir išspręsti šią problemą,
ir mes turime sustabdyti Rekursija kažkur,
mes tikriausiai norite sustabdyti tai kai mes gauti iki 1.
Mes nenorime sustoti prieš tai.
>> Taigi, jei mes apibrėžti Mūsų faktorialas funkcija,
čia už skeletas kaip mes galime tai padaryti.
Mums reikia prijungti šių dviejų Quake bazinį scenarijų ir grįžtamojo atveju.
Kas bazinį scenarijų?
Jei n yra lygus 1, grįžti 1-- tai tikrai paprasta problemą išspręsti.
>> 1 faktorialas yra 1.
Tai ne 1 kartų nieko.
Tai tik 1.
Tai labai paprasta faktas.
Ir taip, kad gali būti mūsų bazinį scenarijų.
Jei mes gauti išlaikė 1 į tai funkcija, mes tiesiog return 1.
>> Koks grįžtamojo atvejis greičiausiai atrodys?
Dėl visų kitų skaičių Be to 1, koks modelis?
Na, jei mes atsižvelgti iš n faktorialas,
Tai n kartų iš n faktorialas atėmus 1.
>> Jei mes radote faktorialas 3, tai 3 kartus 3 minus 1 faktorialas,
arba 2.
Ir todėl, jei mes ne žiūri 1, priešingu atveju
grąža n kartų faktorialas n minus 1.
Tai gana paprasta.
>> Ir dėl turintys šiek tiek labui švaresnis ir labiau elegantiškas kodas,
žino, kad jei mes turime viena linija kilpų arba vieno linija sąlyginės filialai,
galime atsikratyti visas garbanotas petnešos aplink juos.
Taigi, mes galime sujungti tai tai.
Tai lygiai tas pats funkcionalumas kaip šis.
>> Aš tiesiog neatimtų garbanotas petnešos, nes ten tik viena eilutė
viduje tų sąlyginių šakų.
Taigi jie elgiasi vienodai.
Jei n yra lygus 1, grąžinti 1.
Priešingu atveju grįžti n kartų iš n minus 1 faktorialas.
Taigi mes darome problemą mažesnis.
Jei n prasideda kaip 5, mes ketiname grįžti 5 kartus 4 faktorialas.
Ir mes pamatysime per minutę, kai mes kalbame apie skambučius stack-- kitoje vaizdo
kur mes kalbame apie skambinti stack-- mes išmokti
apie tai, kodėl būtent šis procesas veikia.
>> Tačiau, nors faktorialas 5 sako grįžti 5 kartus faktorialas 4 ir 4
ketina pasakyti, gerai, gerai, grąžinimo 4 kartus 3 faktorialas.
Ir, kaip matote, mes Rūšiuoti artėja 1 d.
Mes vis arčiau ir priartinti prie pagrindo atveju.
>> Ir kai mes paspauskite pagrindą, visi ankstesnių funkcijų
turi atsakyti jie ieško.
Faktorinė 2 kalbėjo grąžą 2 kartus 1 faktorialas.
Na, faktorinė iš 1 grąža 1 d.
Taigi už faktorialas skambutis 2 gali grąžinti 2 kartus 1
ir duoti, kad atgal į Faktorialas 3, kuri yra laukia, kad rezultatas.
>> Ir tada jis gali apskaičiuoti jos rezultatas, 3 kartus 2 6,
ir duoti jį atgal į faktorialas 4.
Ir vėl, mes turime Vaizdo skambučių kamino
kur tai yra pavaizduotas šiek tiek daugiau nei tai, ką aš sakau dabar.
Bet tai jis.
Vien tai yra, kad sprendimas Skaičiuojant skaičiaus faktorialas.
>> Tai tik keturias eilutes kodo.
Tai gana kietas, tiesa?
Tai tipo seksualus.
>> Taigi, apskritai, bet ne visada, rekursywny funkcija
gali pakeisti kilpa ne rekursywny funkcija.
Taigi čia, side by side, yra iteracinis versija Faktorialaus funkcija.
Abu šie Skaičiuoti lygiai tas pats dalykas.
>> Jie abu apskaičiuoti n faktorialas.
Kairėje versija naudoja rekursija tai padaryti.
Dešinėje versija naudoja iteracijos tai padaryti.
>> Ir pranešimas, turime pripažinti kintamasis sveikas produktas.
Ir tada mes kilpa.
Tol, kol n yra didesnis už 0, mes išlaikyti padauginus n produktą
ir mažėjančio n iki mes galime apskaičiuoti produktą.
Taigi, šie du funkcijos, vėl, padaryti lygiai tą patį.
Tačiau jie neturi daryti lygiai taip pat.
>> Dabar, tai yra įmanoma, kad turi daugiau nei vieną bazę
atveju arba daugiau nei vieną rekursywny atveju, priklausomai nuo
ką jūsų funkcija bando daryti.
Jūs nebūtinai tik " vieną bazinį scenarijų arba vieno rekursywny
atveju.
Taigi AN kažką pavyzdys su keliais baziniais atvejais
gali būti this-- Fibonačio skaičius, seka.
>> Jūs galite prisiminti iš pradinių mokyklų dienų
kad Fibonačio seka apibrėžta kaip this-- pirmasis elementas yra 0.
Antrasis elementas yra 1.
Abu jie yra tiesiog pagal apibrėžimą.
>> Tada kiekvienas kitas elementas apibrėžiamas kaip n minus 1 ir n minus 2 suma.
Taigi trečiąjį elementą Būtų 0 ir 1 yra 1.
Ir tada ketvirtas elementas būtų antra elementas, 1,
plius trečiasis elementas, 1.
Ir tai būtų 2.
Ir taip toliau, ir taip toliau.
>> Taigi šiuo atveju, mes turime dvi bazines bylas.
Jei n yra lygus 1, grąžinti 0.
Jei n yra lygus 2, grąžinti 1.
Priešingu atveju, grįžti Fibonacci n atėmus 1 plius Fibonačio n ± 2.
>> Taigi, kad kelis bazinius atvejus.
Ką apie kelių rekursyvių atvejais?
Na, kažkas vadinamas Collatz spėjimas.
Nesiruošiu sakyti, jūs žinote, kas tai yra,
nes tai tikrai mūsų galutinis problema šiuo konkrečiu vaizdo.
Ir tai mūsų pratybos dirbti kartu.
>> Taigi čia ką Collatz spėjimas is--
jis taikomas kiekvieną teigiamą sveikąjį skaičių.
Ir tai spėja, kad tai visada galima grįžti
1, jei atlikite šiuos veiksmus.
Jei n yra 1, sustabdyti.
Mes turime grįžti į 1, jei n yra 1.
>> Priešingu atveju, eiti per tai procesas vėl n padalytą iš 2.
Ir pamatyti, jei jūs galite gauti atgal į 1.
Priešingu atveju, jei n yra nelyginis, eiti per šis procesas vėl 3N plius 1,
arba 3 kartus n plius 1.
Taigi čia mes turime vieną bazinį scenarijų.
Jei n yra lygus 1, sustabdyti.
Mes nedarome, bet daugiau rekursija.
>> Bet mes turime dvi rekursinių atvejus.
Jei n yra lygus, mes darome vieną rekursinį atveju, ragindamas N padalytą iš 2.
Jei n yra nelyginis, mes skirtingi rekursywny byla dėl 3 times n plius 1 d.
>> Ir taip už šį video tikslas imtis sekundę, pristabdyti vaizdo įrašą,
ir pabandyti ir rašau tai rekursywny funkcija Collatz
kur praeiti vertės n ir jis apskaičiuoja, kiek žingsnių jį
mano, kad gauti 1, jei jums pradėti iš n ir atlikite šiuos veiksmus iki viršaus.
Jei n yra 1, tai užima 0 žingsnius.
Priešingu atveju, jis ketina išgerkite vieną žingsnį plius tačiau
daug žingsnių jis pasiima arba n padalintas iš 2, jei n yra lygus, ar 3n plius 1
jei n yra keista.
>> Dabar, aš supakuoti ekrane čia Bandinių dalykų už jus pora,
testų atvejais pora jums, norėdami pamatyti, ką šie įvairūs COLLATZ numeriai,
ir taip pat iliustracija iš žingsnių, kad
reikia išgyveno todėl jūs galite rūšiuoti pamatyti šį procesą veiksmų.
Taigi, jei n yra lygus 1, Collatz n yra 0.
Jūs neturite daryti nieko grįžti iki 1.
Jūs jau esate ten.
>> Jei n yra 2, tai užima vienas žingsnis gauti iki 1.
Jūs pradedate su 2.
Na, 2 yra ne lygus 1.
Taigi, tai bus vienas žingsnis plius Tačiau daugelis veiksmų, kurių ji
įgauna N padalytą iš 2.
>> 2, padalytą iš 2 1.
Taigi ji mano vieną žingsnį plius tačiau daug žingsnių užtrunka 1 d.
1 užtrunka nulį veiksmus.
>> 3, kaip matote, yra nemažai etapus.
Nueini iš 3.
Ir tada jūs einate į 10, 5, 16, 8, 4, 2, 1.
Tai užtrunka septynių žingsnių grįžti prie 1 d.
Ir, kaip matote, ten pora kitų bandymų atvejus čia
išbandyti savo programą.
Taigi dar kartą, pristabdyti vaizdo įrašą.
Ir aš eisiu šokti atgal dabar kas tikrasis procesas yra čia
ką tai hipotezė yra.
>> Žr jeigu jūs galite išsiaiškinti Kaip apibrėžti COLLATZ n
taip, kad jis skaičiuoja, kiek žingsniai užtrunka gauti iki 1.
Taigi tikiuosi, jūs sustabdytas video o jūs ne tik manęs laukia
kad turėtumėte atsakyti čia.
Bet jei jūs esate, gerai, Štai atsakymas vistiek.
>> Taigi čia galima apibrėžimas iš Collatz funkcija.
Mūsų bazė case-- jei n yra lygus 1, mes grįžti 0.
Ji neatsižvelgia į bet žingsnių grįžti prie 1 d.
>> Priešingu atveju, mes turime du rekursinį cases-- vienas net numerius ir vienas keista.
Kaip aš išbandyti net numerius yra patikrinti, ar n mod 2 yra lygus 0.
Tai yra, iš esmės, vėl, klausia klausimą,
Jei prisimenate ką mod is-- jei aš skaldyk N iš 2 ten nėra likusi?
Kad būtų lyginis skaičius.
>> Ir todėl, jei n mod 2 yra lygus 0 yra bandymai yra tai lyginis skaičius.
Jei taip, aš noriu grįžti 1, nes tai tikrai
atsižvelgiant vieną žingsnį plius COLLATZ dėl kokia numeris yra pusė mane.
Priešingu atveju, aš noriu grįžti 1 plius Collatz 3 times n plius 1.
Kad buvo kita rekursywny žingsnis, kad mes
galėtų apskaičiuoti Collatz-- žingsnių skaičių
ji mano, kad grįžti 1 suteikiamas numeris.
Taigi tikiuosi, šis pavyzdys padovanojo tau truputį
iš rekursyvių procedūrų skonį.
Tikimės, kad jūs manote kodas yra tiek gražesnė jei bus įgyvendintos
elegantiškas, grįžtamojo būdu.
Bet net jei ne, rekursija yra tikrai galingas įrankis vis.
Ir taip tai tikrai kažkas gauti savo galvą aplink,
nes jūs galėsite sukurti pretty cool programas, naudojant rekursija
kad priešingu atveju būtų sudėtinga rašyti jei jūs naudojate kilpos ir iteracijos.
Aš Doug Lloyd.
Tai CS50.