[Muusika mängib] 

DOUG LLOYD: Sa ilmselt arvad, et koodi kasutatakse vaid täita ülesanne. Sa kirjutad selle välja. Ta teeb midagi. See on päris palju see. 

Sa kompileerida. Sa käivitada programmi. Sa oled hea minna. 

Aga uskuge või mitte, kui te kodeerida kaua, sa tegelikult võiks tulla, et näha, kood midagi, mis on ilus. See lahendab probleemi väga huvitav viis, või seal on lihtsalt midagi väga puhas kohta, kuidas ta välja näeb. Sa võid olla naeravad mind, aga see on tõsi. Ja recursion on üks viis et omamoodi saada see idee ilus, elegantne välimusega koodi. See lahendab probleemid viisil, mis on huvitav, lihtne visualiseerida, ja üllatavalt lühike. 

Tee recursion tööd on rekursiivse funktsiooni defineeritakse funktsioon, mis nõuab ise osa selle täitmist. See võib tunduda natuke imelik, ja me näeme natuke kuidas see töötab hetkel. Aga jälle need rekursiivne protseduurid saab olema nii elegantne sest nad ei kavatse Selle probleemi lahendamiseks ilma kõik need teised funktsioonid või need pikad silmad. Sa näed, et need rekursiivne protseduurid hakkavad otsima nii lühike. Ja nad tõesti ei kavatse teha oma koodi vaatama palju ilusam. 

Ma toon ühe näite Selle näha, kuidas rekursiivne korras võib kindlaks määrata. Nii et kui sa oled tuttav alates matemaatika klassi aastaid tagasi, seal on midagi, mida nimetatakse faktoriaaliga funktsiooni, mis on tavaliselt tähistatakse hüüumärk, mis defineeritakse üle kõik positiivsed täisarvud. Ja nii, et n faktoriaali arvutamiseks on sul korrutada kõik numbrid alla või võrdne n together-- kõik täisarvud alla või võrdne n koos. 

Nii 5 faktoriaal 5 korda 4 korda 3 korda 2 korda 1. Ja 4 faktoriaal 4 korda 3 korda 2 korda 1 ja nii edasi. Sa saad idee. 

Kuna programmeerijad, me ei kasutada n, hüüumärk. Nii me määratleda faktoriaali funktsiooni fakt n. Ja me kasutame faktoriaali luua rekursiivne lahendus probleemile. Ja ma arvan, et te võite leida et see on palju rohkem visuaalselt Palve kui iteratiivne versioon sellest, mida me ka heita pilk ühe hetkega. 

Nii et siin on paar facts-- pun intended-- umbes factorial-- faktoriaali funktsiooni. Faktoriaali 1, nagu ma ütlesin, on 1. Faktoriaali 2 on 2 korda 1. Faktoriaali 3 on 3 korda 2 korda 1, ja nii edasi. Rääkisime 4 ja 5 juba. 

Aga vaadates seda, ei ole see tõsi? Kas pole faktoriaali 2 lihtsalt 2 korda Faktoriaalse 1? Ma mõtlen, faktoriaali 1 on 1. Miks me ei võiks lihtsalt öelda, et alates faktoriaali 2 on 2 korda 1, tegelikult on see vaid 2 korda faktoriaali 1? 

Ja siis laiendada seda mõtet, ei ole faktoriaali 3 vaid 3 korda faktoriaali 2? Ja faktoriaali 4 on 4 korda faktoriaali 3 ja nii edasi? Tegelikult Faktoriaalse mis tahes arvu saab lihtsalt väljendatakse kas me sellist ning viia see läbi igavesti. Me võime liiki üldistada faktoriaali probleem kui see on n korda faktoriaali n miinus 1. On n korda produktist kõik numbrid vähem kui mulle. 

See mõte on see üldistus probleem, võimaldab meil rekursiivselt määratleda faktoriaali funktsiooni. Kui teil määratleda funktsiooni rekursiivselt, seal on kaks asja, mis peavad olema osa sellest. Sa pead olema midagi, mida nimetatakse aluspõhimõtted, mis siis, kui vajutad seda, peatub rekursiivne protsessi. 

Muidu funktsioon, mis nõuab itself-- nagu võite imagine-- võiks kesta igavesti. Funktsioon nõuab funktsiooni nõuab funktsiooni kõned funktsioon nõuab funktsiooni. Kui sul ei ole nii peatada, oma programmi saab tõhusalt kinni kell lõputu silmuse. See krahhi lõpuks, sest see saab otsa mälu. Aga see on kõrval punkti. 

Meil peab olema muul viisil peatada asju peale meie programmi krahh, sest programm, mis jookseb on Tõenäoliselt ei ilus ega elegantne. Ja nii me nimetame seda aluspõhimõtted. See on lihtne lahendus probleemile, mis peatab rekursiivne protsessi tekkimist. Nii et üks osa rekursiivne funktsioon. 

Teine osa on rekursiivne puhul. Ja see on koht, kus recursion tegelikult toimub. See on koht, kus funktsiooni helistab ise. 

See ei helista ise täpselt Samamoodi oli kutsutud. See oleks väike erinevus mis muudab probleemi see püüab lahendada Teeny natuke väiksem. Aga see üldiselt paneb selle lahendada põhiosa lahendus teise kõne sätestatakse rida. 

Milline neist paistab nagu aluspõhimõtted siin? Kumb neist näeb välja nagu Lihtsaim lahendus probleemile? Meil on hunnik faktoriaalid, ja me võiks jätkata läheb nüüd-- 6, 7, 8, 9, 10, ja nii edasi. 

Aga üks neist näeb välja nagu heal juhul olla aluspõhimõtted. See on väga lihtne lahendus. Me ei pea midagi erilist. 

Faktoriaali 1 on lihtsalt 1. Me ei pea tegema muud korrutamine üldse. Tundub, kui me läheme proovida ja seda probleemi lahendada, ja me peame lõpetama recursion kuskil, me ilmselt ei taha enam see, kui saame 1. Me ei taha enam enne seda. 

Nii et kui me määratleda Meie faktoriaali funktsiooni, siin on luukere kuidas me võiksime seda teha. Meil on vaja ühendada need kaks things-- aluspõhimõtted ja rekursiivne puhul. Mis aluspõhimõtted? Kui n on võrdne 1, tagastab 1-- see on väga lihtne probleem lahendada. 

Faktoriaali 1 on 1. See ei ole 1 korda midagi. See on lihtsalt 1. See on väga lihtne tõsiasi. Ja nii, et võib olla meie tugipunkt. Kui me saada edasi 1 sellesse funktsiooni, me lihtsalt tagasi 1. 

Mis on rekursiivne juhul tõenäoliselt välja nägema? Sest iga teine ​​number peale 1, mis on muster? Noh, kui me võtmist faktoriaali n, see on n korda faktoriaali n miinus 1. 

Kui me võtta faktoriaali 3, see on 3 korda faktoriaali 3 miinus 1, või 2. Ja kui me ei ole Vaadates 1, vastasel tagastamise n korda faktoriaali n miinus 1. See on üsna lihtne. 

Ja huvides võttes kergelt puhtam ja elegantne koodi tean, et kui meil on ühe-line silmad või ühekordse joonega tingimisi oksad, saame vabaneda kõik looksulg ümber. Nii saame tugevdada seda sellele. See on täpselt sama funktsionaalsus, sest see. 

Ma lihtsalt tunnen ära lokkis traksid, sest seal on ainult üks rida sees neid tingimisi oksad. Nii et need toimivad sarnaselt. Kui n on võrdne 1, tagastab 1. Vastasel tagasi n korda faktoriaali n miinus 1. Nii et me teeme probleem väiksem. Kui n hakkab läbi 5, me ei kavatse tagasi 5 korda faktoriaali 4. Ja me näeme mõne hetke, kui me räägime umbes kõne stack-- teise video kus me räägime helistada stack-- õpime miks just see protsess toimib. 

Aga samas faktoriaali 5 ütleb naasta üle 5 korra faktoriaali 4 ja 4 läheb öelda, OK, noh, tagastamise 4 korda faktoriaali 3. Ja nagu näete, me oleme omamoodi läheneb 1. Me lähemale ja lähemale, et aluspõhimõtted. 

Ja kui me tabanud base juhul, kõik eelmise funktsioonid on vastus nad otsivad. Factorial 2 ütles vastutasuks 2 korda faktoriaali 1. Noh, faktoriaali 1 tagastab 1. Nii et üleskutse faktoriaali 2 võib naasta 2 korda 1, ja anda see tagasi faktoriaali 3, mis ootab, et tulemus. 

Ja siis ta saab arvutada selle tulemusena 3 korda 2 on 6, ja anda see tagasi faktoriaali 4. Ja jälle oleme video pinu kus see on illustreeritud natuke rohkem kui see, mida ma räägin praegu. Aga see on see. Ainuüksi see on lahendus arvutamisel faktoriaali number. 

See on ainult neli rida koodi. See on päris lahe, eks? See on selline seksikas. 

Nii üldiselt, kuid mitte alati, rekursiivne funktsioon võib asendada Silmusjuhtme mitte rekursiivne funktsioon. Nii et siin kõrvuti, on iteratiivne versioon Faktoriaalse funktsiooni. Mõlemad Arvuta täpselt sama asi. 

Nad mõlemad arvutada faktoriaali n. Versioon vasakul kasutab recursion seda teha. Versioon paremal kasutab iteratsiooni seda teha. 

Ja teate, meil on kuulutada Muutuva täisarv toodet. Ja siis me loop. Nii kaua, kui n on suurem kui 0, me hoida korrutades selle toote n ja decrementing n kuni me arvutada ka. Nii need kaks ülesannet jällegi teha täpselt sama asja. Aga nad ei tee seda täpselt samamoodi. 

Nüüd on võimalik on rohkem kui üht alust juhtumi või rohkem kui üks rekursiivne juhul, sõltuvalt mida teie ülesanne on püüdnud teha. Sa ei pruugi piirdu ainult ühe aluse puhul või ühe rekursiivse juhul. Nii näiteks midagi mitu baasi juhtudel Võib olla see-- Fibonacci jada jada. 

Nette alates algkool päeva et Fibonacci jada määratletud nagu see-- esimene element on 0. Teine element on 1. Mõlemad neist on lihtsalt definitsiooni. 

Siis iga teine ​​element on määratletud summana n miinus 1 ja n miinus 2. Nii kolmas element oleks 0 pluss 1 on 1. Ja siis neljas element Oleks teine ​​element, 1, pluss kolmas element, 1. Ja et oleks 2. Ja nii edasi ja nii edasi. 

Nii et kui meil on kaks alust juhtudel. Kui n on võrdne 1, tagastab 0. Kui n on võrdne 2, tagasi 1. Vastasel juhul tagastab Fibonacci n miinus 1 pluss Fibonacci n miinus 2. 

Nii et mitu baasi juhtudel. Aga mitu rekursiivne juhtudel? Noh, seal on midagi nimetatakse Collatz oletustele. Ma ei hakka ütlema, sa tead, mis see on, sest see on tegelikult meie lõplik Probleem selle konkreetse video. Ja see on meie harjutus töötada koos. 

Nii et siin on, mida Collatz oletustele on-- see kehtib iga positiivne täisarv. Ja see spekuleerib, et see on alati võimalik tagasi saada 1, kui te järgite neid samme. Kui n on 1, peatus. Meil tagasi 1 kui n on 1. 

Muidu läheb läbi selle Meetod uuesti n jagatuna 2. Ja vaata, kas saad tagasi 1. Vastasel juhul, kui n on paaritu, läbida Selle protsessi uuesti 3n + 1, või 3 korda n pluss 1. Nii et siin on meil ühe aluse puhul. Kui n on võrdne 1, peatus. Me ei tee enam recursion. 

Aga meil on kaks rekursiivne juhtudel. Kui n on paarisarv, teeme ühe rekursiivse Juhul, kutsudes n jagatud 2. Kui n on paaritu, teeme erinev rekursiivne juhul 3 korda n + 1. 

Ja nii eesmärk see video on võtma teise, Video peatamiseks ja püüa kirjutada seda rekursiivne funktsioon Collatz kus te kaotate oma väärtuse n, ja arvutab, kui palju samme selle võtab, et saada 1, kui te alustate n ja te järgite neid samme kuni eespool. Kui n on 1, kulub 0 samme. Vastasel juhul läheb võta üks samm pluss aga palju samme, mis kulub kas n jagatuna 2, kui n on paaris või 3n pluss 1 kui n on paaritu. 

Nüüd ma panin ekraanil siin paar testi jaoks midagi paar testid juhtudel sulle, et näha mida need erinevad Collatz numbrid, ning samuti illustratsioon samme, mis tuleb läbi käinud, nii et saate omamoodi näha selle protsessi tegevuse. Seega, kui n on võrdne 1, Collatz n on 0. Sa ei pea tegema midagi tagasi saada 1. Sa oled juba seal. 

Kui n on 2, kulub üks samm, et saada 1. Sa alustad 2. Well, 2 ei võrdu 1. Nii et see saab olema üks samm pluss aga palju samme selle võtab n jagatuna 2. 

2 jagatuna 2 on 1. Nii kulub ühe sammu pluss aga palju samme, mis kulub 1. 1 võtab null samme. 

3, kui näed, seal on päris mitmeid etappe. Lähed 3. Ja siis lähete 10, 5, 16, 8, 4, 2, 1. See võtab seitse sammu, et saada tagasi 1. Ja nagu näete, seal on Paar teiste test juhtudel siin katsetada oma programmi. Nii jälle pausi video. Ja ma lähen tagasi hüpata nüüd mida tegelik protsess on siin, mida see hüpotees on. 

Vaadake, kas saate aru saada kuidas määratleda Collatz n nii, et see arvutab mitu astub ta võtab, et saada 1. Loodetavasti olete peatatud video ja sa ei ole lihtsalt ootab mind teile vastuse siin. Aga kui sa oled, noh, siin on vastus nagunii. 

Nii et siin on võimalik määratlus on Collatz funktsiooni. Meie baasi case-- kui n on võrdub 1, naaseme 0. See ei võta samme, et saada tagasi 1. 

Muidu on meil kaks rekursiivne cases-- üks isegi numbreid ja üks veider. Kuidas ma test isegi numbrid on vaadata, kui n mod 2 võrdub 0. See on põhiliselt jällegi küsib küsimuse, Kui te mäletate, milline mod on-- kui ma lõhe n 2 ei puudu jäänud? See oleks paarisarv. 

Ja nii, kui n mod 2 võrdub 0 on testimine on see paarisarv. Kui jah, ma tahan tagasi 1 sest see on kindlasti võttes üks samm pluss Collatz kohta mis iganes number on pool mind. Muidu ma tahan tagasi 1 pluss Collatz 3 korda n + 1. See oli teine rekursiivne samm, et me võiks võtta, et arvutada Collatz-- sammude arv kulub, et saada tagasi 1 antud number. Loodetavasti on see näiteks saatis sulle natuke ja maitse rekursiivne korra. Loodetavasti te arvate, kood on vähe ilusamaks, kui rakendatakse elegantne, rekursiivne viis. Aga isegi kui ei ole, recursion on tõesti võimas vahend sellegipoolest. Ja nii see on kindlasti midagi saada oma peas ümber, sest sa pead olema võimeline looma päris lahe programme kasutades recursion mis muidu oleks keeruline kirjutada kui te kasutate silmad ja korduse. Ma olen Doug Lloyd. See on CS50.