[Prehrávanie hudby] 

DOUG LLOYD: Pravdepodobne si myslí, že kód slúži len na splnenie úlohy. Píšete si to. Je to niečo robí. To je celkom veľa to. 

Tie skompilovať. Spustite program. Si dobré ísť. 

Ale verte tomu alebo nie, ak je si kód na dlhú dobu, ste vlastne môže prísť vidieť kód ako niečo, čo je krásne. To rieši problém v Veľmi zaujímavý spôsob, alebo tam je proste niečo, čo naozaj čistý o tom, ako to vyzerá. Tie by mohli byť smiať sa na mňa, ale je to pravda. A rekurzia je jedným zo spôsobov, sa nejako dostať túto myšlienku krásne, elegantné vyzerajúce kód. To rieši problémy, spôsoby, ktoré sú zaujímavé, ľahko predstaviť, a prekvapivo krátke. 

Spôsob, akým funguje rekurzia je, rekurzívne funkcie je definovaný ako funkcia, ktorá volá sám ako súčasť jeho vykonanie. To sa môže zdať trochu divné, a uvidíme trochu o tom, ako to funguje v okamihu. Ale opäť, tieto rekurzívne postupy sú Bude tak elegantné pretože idú na riešenie tohto problému, bez toho, aby ktoré majú všetky tieto ostatné funkcie alebo tieto dlhé slučky. Uvidíte, že tieto rekurzívne postupy sú bude vyzerať tak krátky. A naozaj sa chystáte robiť váš kód vyzerať oveľa krajšie. 

Dám vám príklad z toho vidieť, ako rekurzívne postup by mohol byť definovaný. Takže ak ste oboznámení s tým od triede math pred mnohými rokmi, Je tu niečo, čo nazýva Funkcia faktoriál, ktorý je zvyčajne označený ako výkričník, ktorý je definovaný cez všetky pozitívne celé čísla. A tak, že n faktoriál sa vypočíta je násobiť všetky čísla menšie ako alebo sa rovná n together-- všetky celé čísla menšie ako alebo rovná n dohromady. 

Takže 5 faktoriál je 5 krát 4 krát 3 krát 2 krát 1. A 4 faktoriál je 4 krát 3 krát 2 krát 1 a tak ďalej. Dostanete nápad. 

Ako programátori, my nie použite N výkričník. Takže budeme definovať faktoriál Funkcie ako fakt n. A budeme používať faktoriál k vytvoreniu rekurzívne riešenie problému. A myslím, že by ste mohli nájsť že je to oveľa viac vizuálne príťažlivý ako iteratívny verzia tohto, čo budeme tiež sa pozrieť na za chvíľu. 

Tak tu je pár facts-- hračka intended-- o factorial-- faktoriál funkcie. Faktoriál 1, ako som povedal, je 1. Faktoriál 2 je 2 krát 1. Faktoriál 3 je 3 krát 2 krát 1, a tak ďalej. Hovorili sme o 4 a 5 už. 

Ale pri pohľade na to, nie je to pravda? Nie je faktoriál 2 len 2 krát faktoriál 1? Myslím, že faktoriál 1 je 1. Tak prečo jednoducho nemôžeme povedať, že, pretože faktoriál 2 je 2 krát 1, je to naozaj len 2 krát faktoriál 1? 

A potom rozšírila túto myšlienku, nie je faktoriál 3 len 3 krát faktoriál 2? A faktoriál 4 je 4 krát faktoriál 3, a tak ďalej? V skutočnosti, faktoriálovej akékoľvek množstvo môže len sa vyjadrí, ak sme trochu o vykonávaní tohto navždy. Môžeme trochu upresniť faktoriál problém ako je to časy n faktoriál n mínus 1. Je to n krát produkt všetky čísla menšie ako ja. 

Táto myšlienka, to zovšeobecnenie problému, nám umožňuje rekurzívne definovať faktoriálu funkcie. Pri definovaní funkcie rekurzívne, je tu dve veci, ktoré musia byť súčasťou toho všetkého. Musíte mať niečo, čo nazýva základný prípad, ktorý, keď ho spustiť, zastaví rekurzívne proces. 

V opačnom prípade funkcie, ktorá volá itself-- ako by sa mohlo imagine-- by mohol pokračovať donekonečna. Funkcia volá funkciu volanie funkcie volania Funkcia volá funkciu. Ak nemáte cestu ho zastaviť, program bude účinne prilepené v nekonečnej slučke. To sa zrúti nakoniec, pretože to bude spustiť z pamäte. Ale to je vedľajšie. 

Potrebujeme mať nejaký iný spôsob, ako zastaviť veci, okrem nášho programu zhadzovať, pretože program, ktorý havaruje je Pravdepodobne nie krásna a elegantná. A tak hovoríme to referenčný prípad. Jedná sa o jednoduché riešenie na problém, ktorý zastavuje proces rekurzívneho výskytu. Takže to je jedna časť rekurzívne funkcie. 

Druhá časť je rekurzívny prípad. A to je miesto, kde rekurzia bude skutočne konať. To je miesto, kde Funkcia zavolá sama. 

Nebude volať seba v presne rovnako tak, ako to bolo volané. Bude to nepatrná zmena ktorá robí problém je to snaží vyriešiť malinký niečo menšie. Ale všeobecne prechádza babku vyriešiť prevažnú časť roztoku na inú výzvu v rade. 

Ktorý z týchto pohľadov ako základné veci tu? Ktorý z týchto vyzerá Najjednoduchším riešením problému? Máme veľa faktoriál, a tak by sme mohli pokračovať sa on-- 6, 7, 8, 9, 10, a tak ďalej. 

Ale jeden z nich vyzerá ako dobrým príkladom, že je referenčný prípad. Je to veľmi jednoduché riešenie. Nemusíme robiť nič zvláštne. 

Faktoriál 1 je len 1. Nemusíme robiť akýkoľvek násobenie vôbec. Vyzerá to, že v prípade, že budeme aby sa pokúsila vyriešiť tento problém, a musíme zastaviť rekurziu niekde, Pravdepodobne chceme zastaviť za to, keď sa dostaneme do 1. Nechceme zastaviť pred tým. 

Takže ak budeme definovať náš faktoriál funkcie, tu je kostra pre ako by sme mohli urobiť. Musíme zapojiť v týchto dvoch things-- základný prípad, a rekurzívne prípad. Čo je to referenčný prípad? Ak je n rovné 1, vrátiť 1-- to je naozaj jednoduchý problém k riešeniu. 

Faktoriál 1 je 1. Nie sú to 1 krát čokoľvek. Je to len 1. Je to veľmi jednoduchý fakt. A tak to môže byť naša základňa prípad. Ak by sme si prešiel 1 do tohto funkcie, jednoducho budeme vracať 1. 

Čo je rekurzívny Prípad pravdepodobne vyzerať? Pre každý iné číslo okrem 1, čo je vzor? No, ak berieme faktoriál n, Je to doba n faktoriál n mínus 1. 

Ak vezmeme faktoriál 3, je to 3 krát faktoriál 3 mínus 1, alebo 2. A tak, keď nie sme pri pohľade na 1, inak return n násobok faktoriál n mínus 1. Je to celkom jednoduché. 

A v záujme mať mierne čistejšie a elegantnejšie kód, vedia, že ak máme jednoriadkové slučky alebo jednoriadkový podmienené vetvy, sa môžeme zbaviť všetky zložené zátvorky okolo nich. Takže môžeme upevniť to k tomu. To má presne rovnaké funkcia je tento. 

Ja som len odnášať kučeravé traky, pretože tam je len jeden riadok vo vnútri týchto podmienených vetiev. Tak to sa správajú rovnako. Ak je n rovné 1, 1 vrátiť. V opačnom prípade vracia n-krát faktoriál n mínus 1. Takže robíme problém menšie. Ak n začína ako 5, ideme vrátiť 5 krát faktoriál 4. A uvidíme za chvíľu, keď hovoríme o volanie stack-- v inom videu kde hovoríme o zavolajte stack-- dozvieme o tom, prečo práve tento proces funguje. 

Ale zatiaľ čo faktoriál 5 hovorí: vrátiť 5 krát faktoriál 4, a 4 sa chystá povedať, OK, dobre, návrat 4 krát faktoriál 3. A ako môžete vidieť, že sme druh blíži 1. Sme stále bližšie a bližšie k tomuto základnému prípadu. 

A akonáhle sme narazili základné veci, všetky predchádzajúce funkcie poznať odpoveď, ktoré hľadali. Faktoriál 2 hovoril návrat 2 krát faktoriál 1. No, faktoriál 1 vráti 1. Takže výzva na faktoriálu 2 môže vrátiť 2 krát 1, a dať to späť do faktoriál 3, ktorý čaká na tento výsledok. 

A potom to môže vypočítať Jej výsledok, 3x 2 je 6, a vráti ho faktoriál 4. A zase, máme video na zásobníku volania kde je to znázornené trochu viac než to, čo hovorím teraz. Ale to je to. To samo o sebe je riešením výpočet faktoriál čísla. 

Je to len štyri riadky kódu. To je celkom v pohode, nie? Je to trochu sexy. 

Takže všeobecne, ale nie vždy, rekurzívne funkcie môže nahradiť slučkou v non-rekurzívne funkcie. Tak tu, vedľa seba, je iteratívny verzia faktoriálnym funkcie. Obe tieto vypočítať presne to isté. 

Oba vypočítať faktoriál n. Verzia na ľavej strane používa rekurziu, ako to urobiť. Verzia na pravej strane využíva opakovanie, ako to urobiť. 

A upozornenie, musíme vyhlásiť, premenná celé číslo produktu. A potom sme slučka. Tak dlho, ako n je väčšie ako 0, sme udržiavať vynásobením tohto výrobku N a dekrementování n, kým spočítame produktu. Takže tieto dve funkcie, opäť, robiť presne to isté. Ale nerobia to v presne rovnakým spôsobom. 

Teraz je možné majú viac ako jednu základňu puzdro alebo viac než jedno rekurzívne prípad, v závislosti o Aká je vaša funkcia snaží robiť. Tie nie sú nevyhnutne len na jediný referenčný prípad alebo jeden rekurzívne prípad. Takže príklad niečoho s viac základňovými prípadoch by mohol byť tohle-- Fibonacci poradové číslo. 

Možno si spomeniete, od základnej školy dní že sekvencie Fibonacci je definovaná ako tohle-- prvý prvok je 0. Druhým prvkom je 1. Obaja to sú len zo svojej podstaty. 

Potom je definovaný každý iný prvok ako súčet n mínus 1 a n mínus 2. Takže tretí prvok by byť 0 plus 1 je 1. A potom štvrtý element by bol druhý prvok, 1, a tretí prvok, 1. A to by bolo 2. A tak ďalej a tak ďalej. 

Takže v tomto prípade, máme dve základné prípady. Ak je n rovné 1, vrátiť 0. Ak je n rovné 2, 1 vrátiť. V opačnom prípade vráti Fibonacci n 1 plus mínus Fibonacci n mínus 2. 

Tak to je viac základné prípady. A čo viac rekurzívnych prípadoch? No, je tu niečo, volal Collatz dohad. Nebudem hovoriť, Viete, čo to je, pretože je to vlastne naša posledná Problémom pre túto konkrétnu video. A to je naša cvičenie pracovať spoločne. 

Tak tu je to, čo Collatz dohad je-- to platí pre každé kladné celé číslo. A to špekuluje, že je to vždy možné sa dostať späť 1, ak budete postupovať podľa týchto krokov. Ak n je 1, zastaviť. Musíme späť na 1, ak n je 1. 

V opačnom prípade, prejsť tento proces opäť na n deleno 2. A uvidíme, či sa môžete vrátiť do 1. V opačnom prípade, ak je n nepárne, prejsť tento proces znovu 3n plus 1, alebo 3 krát n a 1. Takže tu máme jednotný referenčný prípad. Ak je n rovné 1, zastaviť. Nerobíme žiadne ďalšie rekurziu. 

Ale my máme dve rekurzívne prípady. Ak n je dokonca, robíme jednu rekurzívne Prípad, volanie n deleno 2. Pokiaľ je n nepárne, robíme iný rekurzívne prípad na 3 krát N plus 1. 

A tak cieľ pre toto video je vziať druhý, video pozastaviť, a pokúsiť sa napísať tento rekurzívne funkcie Collatz kde odovzdáte v hodnote n, a to spočíta, koľko krokov to znamená dostať na hodnotu 1, ak spustíte z n a budete postupovať tieto kroky hore. Ak n je 1, to trvá 0 krokov. V opačnom prípade, bude to jeden krok navyše však rad krokov to trvá na oboch n delené 2, ak n je dokonca, alebo 3n plus 1 ak n je nepárne. 

Teraz som dal na obrazovke tu pár skúšobných vecí pre vás, pár testov prípadov pre vás, vidieť čo tieto rôzne počty Collatz sú, a tiež ilustrácie z krokov, ktoré Treba prešiel, takže môžete druh vidieť tento proces v akcii. Takže ak n je rovné 1, Collatz n je 0. Nemusíte robiť niečo dostať sa späť do 1. Už si už tam. 

Ak n je 2, trvá jeden krok sa dostať do 1. Začnete s 2. Tak, 2 nie je rovné 1. Takže to bude jeden krok plus však veľa krokoch, berie na n deleno 2. 

2 deleno 2 je 1. Takže to trvá jeden krok navyše však rad krokov trvá 1. 1. berie nula kroky. 

Pre 3, ako môžete vidieť, je tu pomerne málo krokov zapojiť. Môžete ísť od 3. A potom idete 10, 5, 16, 8, 4, 2, 1. To trvá sedem krokov dostať sa späť do 1. A ako môžete vidieť, je tu pár ďalších testovacích prípadov tu vyskúšať program. Takže znovu, video pozastaviť. A ja pôjdem skočiť späť teraz čo je skutočný proces je tu, čo to je dohad. 

Uvidíme, či môžete prísť na to, ako definovať Collatz n tak, aby sa vypočíta, koľko kroky trvá dostať na 1. Takže dúfajme, že ste sa zastavil video a nie ste práve na mňa čakajú aby vám odpoveď tu. Ale ak ste dobre, tu je odpoveď rovnako. 

Tak tu je možná definícia funkcie Collatz. Naša základňa case-- ak n je rovné 1, vrátime 0. Neznamená to však trvať akýkoľvek Kroky sa dostať späť do 1. 

Inak máme dve rekurzívne cases-- jeden pre párne čísla a jeden pre nepárne. Spôsob, akým som test na párnych čísel je skontrolovať, či n mod 2 = 0. To je v podstate, opäť, pýtať na otázku, Ak si spomínate, čo mod je-- keby som rozdeliť n o 2 neexistuje žiadny zvyšok? To by byť párne číslo. 

A tak, keď n mod 2 = 0 je testovanie je to párne číslo. Ak áno, chcem sa vrátiť 1, preto, že to je určite pričom jeden krok navyše Collatz z bez ohľadu na počet je polovica zo mňa. Inak by som sa chcel vrátiť 1 plus Collatz 3 krát n a 1. To bol druhý rekurzívne krok, ktorý sme mohol vziať na výpočet Collatz-- počet krokov to znamená dostať späť na 1 pridelené číslo. Tak dúfajme, že tento príklad ti dal trochu z chuti rekurzívnych postupov. Dúfajme, že si myslíte, že kód je niečo krajšie, ak budú vykonané v elegantnom, rekurzívne spôsobom. Ale aj keď nie, rekurzia je naozaj mocný nástroj však. A tak je to určite niečo, dostať hlavu okolo, pretože budete môcť vytvoriť celkom v pohode programy pomocou rekurzia ktoré by inak mohli byť zložité písať ak používate slučky a iterácie. Som Doug Lloyd. To je CS50.