[Přehrávání hudby] 

DOUG LLOYD: Pravděpodobně si myslí, že kód slouží jen ke splnění úkolu. Píšete si to. Je to něco dělá. To je docela hodně to. 

Ty zkompilovat. Spusťte program. Jsi dobré jít. 

Ale věřte tomu nebo ne, je-li si kód na dlouhou dobu, jste vlastně může přijít vidět kód jako něco, co je krásné. To řeší problém v Velmi zajímavý způsob, nebo tam je prostě něco, co opravdu čistý o tom, jak to vypadá. Ty by mohly být smát se na mě, ale je to pravda. A rekurze je jedním ze způsobů, se nějak dostat tuto myšlenku krásné, elegantní vypadající kód. To řeší problémy, způsoby, které jsou zajímavé, snadno představit, a překvapivě krátké. 

Způsob, jakým funguje rekurze je, rekurzivní funkce je definován jako funkce, která volá sám jako součást jeho provedení. To se může zdát trochu divné, a uvidíme trochu o tom, jak to funguje v okamžiku. Ale opět, tyto rekurzivní postupy jsou Bude tak elegantní protože jdou k řešení tohoto problému, aniž by které mají všechny tyto ostatní funkce nebo tyto dlouhé smyčky. Uvidíte, že tyto rekurzivní postupy jsou bude vypadat tak krátký. A opravdu se chystáte dělat váš kód vypadat mnohem krásnější. 

Dám vám příklad z toho vidět, jak rekurzivní postup by mohl být definován. Takže pokud jste obeznámeni s tím od třídě math před mnoha lety, Je tu něco, co nazývá Funkce faktoriál, který je obvykle označený jako vykřičník, který je definován přes všechny pozitivní celá čísla. A tak, že n faktoriál se vypočítá je násobit všechny čísla menší než nebo se rovná n together-- všechna celá čísla menší než nebo rovna 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 dále. Dostanete nápad. 

Jako programátoři, my ne použijte N vykřičník. Takže budeme definovat faktoriál Funkce jako fakt n. A budeme používat faktoriál k vytvoření rekurzivní řešení problému. A myslím, že byste mohli najít že je to mnohem víc vizuálně přitažlivý než iterativní verze tohoto, což budeme také se podívat na za chvíli. 

Tak tady je pár facts-- hříčka intended-- o factorial-- faktoriál funkce. Faktoriál 1, jak jsem řekl, je 1. Faktoriál 2 je 2 krát 1. Faktoriál 3 je 3 krát 2 krát 1, a tak dále. Mluvili jsme o 4 a 5 již. 

Ale při pohledu na to, není to pravda? Není faktoriál 2 jen 2 krát faktoriál 1? Myslím, že faktoriál 1 je 1. Tak proč prostě nemůžeme říct, že, protože faktoriál 2 je 2 krát 1, je to opravdu jen 2 krát faktoriál 1? 

A pak rozšířila tuto myšlenku, není faktoriál 3 jen 3 krát faktoriál 2? A faktoriál 4 je 4 krát faktoriál 3, a tak dále? Ve skutečnosti, faktoriální jakékoliv množství může jen se vyjádří, pokud jsme trochu o provádění tohoto navždy. Můžeme trochu zobecnit faktoriál problém jak je to časy n faktoriál n minus 1. Je to n krát produkt všechna čísla menší než já. 

Tato myšlenka, to zobecnění problému, nám umožňuje rekurzivně definovat faktoriálu funkce. Při definování funkce rekurzivně, je tu dvě věci, které musí být součástí toho všeho. Musíte mít něco, co nazývá referenční případ, který, když jej spustit, zastaví rekurzivní proces. 

V opačném případě funkce, která volá itself-- jak by se mohlo imagine-- by mohl pokračovat donekonečna. Funkce volá funkci volání funkce volání Funkce volá funkci. Pokud nemáte cestu jej zastavit, program bude účinně přilepená v nekonečné smyčce. To se zhroutí nakonec, protože to bude spustit z paměti. Ale to je vedlejší. 

Potřebujeme mít nějaký jiný způsob, jak zastavit věci, kromě našeho programu shazovat, protože program, který havaruje je Pravděpodobně ne krásná a elegantní. A tak říkáme to referenční případ. Jedná se o jednoduché řešení na problém, který zastavuje proces rekurzivního výskytu. Takže to je jedna část rekurzivní funkce. 

Druhá část je rekurzivní případ. A to je místo, kde rekurze bude skutečně konat. To je místo, kde Funkce zavolá sama. 

Nebude volat sebe v přesně stejně tak, jak to bylo voláno. Bude to nepatrná změna která dělá problém je to snaží vyřešit malinký něco menší. Ale obecně prochází babku vyřešit převážnou část roztoku na jinou výzvu v řadě. 

Který z těchto pohledů jako základní věci tady? Který z těchto vypadá Nejjednodušším řešením problému? Máme spoustu faktoriály, a tak bychom mohli pokračovat se on-- 6, 7, 8, 9, 10, a tak dále. 

Ale jeden z nich vypadá jako dobrým příkladem, že je referenční případ. Je to velmi jednoduché řešení. Nemusíme dělat nic zvláštního. 

Faktoriál 1 je jen 1. Nemusíme dělat jakýkoli násobení vůbec. Vypadá to, že v případě, že budeme aby se pokusila vyřešit tento problém, a musíme zastavit rekurzi někde, Pravděpodobně chceme zastavit za to, když se dostaneme do 1. Nechceme zastavit před tím. 

Takže pokud budeme definovat náš faktoriál funkce, tady je kostra pro jak bychom mohli udělat. Musíme zapojit v těchto dvou things-- referenční případ, a rekurzivní případ. Co je to referenční případ? Je-li n rovno 1, vrátit 1-- to je opravdu jednoduchý problém k řešení. 

Faktoriál 1 je 1. Nejsou to 1 krát cokoliv. Je to jen 1. Je to velmi jednoduchý fakt. A tak to může být naše základna případ. Pokud bychom si prošel 1 do tohoto funkce, prostě budeme vracet 1. 

Co je rekurzivní Případ pravděpodobně vypadat? Pro každý jiné číslo kromě 1, co je vzor? No, pokud bereme faktoriál n, Je to doba n faktoriál n minus 1. 

Pokud vezmeme faktoriál 3, je to 3 krát faktoriál 3 minus 1, nebo 2. A tak, když nejsme při pohledu na 1, jinak return n násobek faktoriál n minus 1. Je to docela jednoduché. 

A v zájmu mít mírně čistší a elegantnější kód, vědí, že pokud máme jednořádkové smyčky nebo jednořádkový podmíněné větve, se můžeme zbavit všechny složené závorky kolem nich. Takže můžeme upevnit to k tomu. To má přesně stejné funkce je tento. 

Já jsem jen odnášet kudrnaté šle, protože tam je jen jeden řádek uvnitř těchto podmíněných větví. Tak to se chovají stejně. Je-li n rovno 1, 1 vrátit. V opačném případě vrací n-krát faktoriál n minus 1. Takže děláme problém menší. Pokud n začíná jako 5, jdeme vrátit 5 krát faktoriál 4. A uvidíme za chvíli, když mluvíme o volání stack-- v jiném videu kde mluvíme o zavolejte stack-- dozvíme o tom, proč právě tento proces funguje. 

Ale zatímco faktoriál 5 říká: vrátit 5 krát faktoriál 4, a 4 se chystá říct, OK, dobře, návrat 4 krát faktoriál 3. A jak můžete vidět, že jsme druh blíží 1. Jsme stále blíž a blíže k tomuto základnímu případu. 

A jakmile jsme narazili základní věci, všechny předchozí funkce znát odpověď, které hledali. Faktoriál 2 říkal návrat 2 krát faktoriál 1. No, faktoriál 1 vrátí 1. Takže výzva k faktoriálu 2 může vrátit 2 krát 1, a dát to zpátky do faktoriálem 3, který čeká na tento výsledek. 

A pak to může vypočítat Její výsledek, 3x 2 je 6, a vrátí jej faktoriálem 4. A zase, máme video na zásobníku volání kde je to znázorněno poněkud víc než to, co říkám teď. Ale to je to. To samo o sobě je řešením výpočet faktoriál čísla. 

Je to jen čtyři řádky kódu. To je docela v pohodě, ne? Je to trochu sexy. 

Takže obecně, ale nikoli vždy, rekurzivní funkce může nahradit smyčkou v non-rekurzivní funkce. Tak tady, vedle sebe, je iterativní verze faktoriálové funkce. Obě tyto vypočítat přesně totéž. 

Oba vypočítat faktoriál n. Verze na levé straně používá rekurzi, jak to udělat. Verze na pravé straně využívá opakování, jak to udělat. 

A upozornění, musíme prohlásit, proměnná celé číslo produktu. A pak jsme smyčka. Tak dlouho, jak n je větší než 0, jsme udržovat vynásobením tohoto výrobku N a dekrementování n, dokud spočítáme produktu. Takže tyto dvě funkce, opět, dělat přesně totéž. Ale nedělají to v přesně stejným způsobem. 

Nyní je možné mají více než jednu základnu pouzdro nebo více než jedno rekurzivní případ, v závislosti o Jaká je vaše funkce snaží dělat. Ty nejsou nutně jen na jediný referenční případ nebo jeden rekurzivní pouzdro. Takže příklad něčeho s více základnovými případech by mohl být tohle-- Fibonacci pořadové číslo. 

Možná si vzpomenete, od základní školy dní že sekvence Fibonacci je definována jako tohle-- první prvek je 0. Druhým prvkem je 1. Oba to jsou jen ze své podstaty. 

Pak je definován každý jiný prvek jako součet n minus 1 a n minus 2. Takže třetí prvek by být 0 plus 1 je 1. A pak čtvrtý element by byl druhý prvek, 1, a třetí prvek, 1. A to by bylo 2. A tak dále a tak dále. 

Takže v tomto případě, máme dvě základní případy. Je-li n rovno 1, vrátit 0. Je-li n rovno 2, 1 vrátit. V opačném případě vrátí Fibonacci n 1 plus minus Fibonacci n minus 2. 

Tak to je více základní případy. A co více rekurzivních případech? No, je tu něco, volal Collatz dohad. Nebudu říkat, Víte, co to je, protože je to vlastně naše poslední Problémem pro tuto konkrétní video. A to je naše cvičení pracovat společně. 

Tak tady je to, co Collatz dohad je-- to platí pro každé kladné celé číslo. A to spekuluje, že je to vždy možné se dostat zpátky 1, pokud budete postupovat podle těchto kroků. Jestliže n je 1, zastavit. Musíme zpátky na 1, pokud n je 1. 

V opačném případě, projít tento proces opět na n děleno 2. A uvidíme, jestli se můžete vrátit do 1. V opačném případě, je-li n liché, projít tento proces znovu 3n plus 1, nebo 3 krát n a 1. Takže tady máme jednotný referenční případ. Je-li n rovno 1, zastavit. Neděláme žádné další rekurzi. 

Ale my máme dvě rekurzivní případy. Pokud n je dokonce, děláme jednu rekurzivní Případ, volání n děleno 2. Pokud je n liché, děláme jiný rekurzivní případ na 3 krát N plus 1. 

A tak cíl pro toto video je vzít druhý, video pozastavit, a pokusit se napsat tento rekurzivní funkce Collatz kde předáte v hodnotě n, a to spočítá, kolik kroků to znamená dostat na hodnotu 1, pokud spustíte z n a budete postupovat tyto kroky nahoře. Pokud n je 1, to trvá 0 kroků. V opačném případě, bude to jeden krok navíc nicméně řada kroků to trvá na obou n děleno 2, pokud n je dokonce, nebo 3n plus 1 pokud n je liché. 

Teď jsem dal na obrazovce zde pár zkušebních věcí pro vás, pár testů případů pro vás, vidět co tyto různé počty Collatz jsou, a také ilustrace z kroků, které Je třeba prošel, takže můžete druh vidět tento proces v akci. Takže pokud n je rovno 1, Collatz n je 0. Nemusíte dělat něco dostat se zpátky do 1. Už jsi už tam. 

Pokud n je 2, trvá jeden krok se dostat do 1. Začnete s 2. Tak, 2 není rovno 1. Takže to bude jeden krok plus nicméně mnoho krocích, bere na n děleno 2. 

2 děleno 2 je 1. Takže to trvá jeden krok navíc nicméně řada kroků trvá 1. 1. bere nula kroky. 

Pro 3, jak můžete vidět, je tu poměrně málo kroků zapojit. Můžete jít od 3. A pak jdete 10, 5, 16, 8, 4, 2, 1. To trvá sedm kroků dostat se zpátky do 1. A jak můžete vidět, je tu pár dalších testovacích případů zde vyzkoušet program. Takže znovu, video pozastavit. A já půjdu skočit zpět teď co je skutečný proces je tady, co to je dohad. 

Uvidíme, jestli můžete přijít na to, jak definovat Collatz n tak, aby se vypočítá, kolik kroky trvá dostat na 1. Takže doufejme, že jste se zastavil video a nejste zrovna na mě čekají aby vám odpověď zde. Ale pokud jste dobře, tady je odpověď stejně. 

Tak tady je možná definice funkce Collatz. Naše základna case-- pokud n je rovné 1, vrátíme 0. Neznamená to však trvat jakýkoli Kroky se dostat zpět do 1. 

Jinak máme dvě rekurzivní cases-- jeden pro sudá čísla a jeden pro liché. Způsob, jakým jsem test na sudých čísel je zkontrolovat, zda n mod 2 = 0. To je v podstatě, opět, ptát na otázku, Pokud si vzpomínáte, co mod je-- kdybych rozdělit n o 2 neexistuje žádný zbytek? To by být sudé číslo. 

A tak, když n mod 2 = 0 je testování je to sudé číslo. Pokud ano, chci se vrátit 1, proto, že to je určitě přičemž jeden krok navíc Collatz z bez ohledu na počet je polovina ze mě. Jinak bych se chtěl vrátit 1 plus Collatz 3 krát n a 1. To byl druhý rekurzivní krok, který jsme mohl vzít pro výpočet Collatz-- počet kroků to znamená dostat zpět na 1 přiděleno číslo. Tak doufejme, že tento příklad ti dal trochu z chuti rekurzivních postupů. Doufejme, že si myslíte, že kód je něco krásnější, jestliže budou provedeny v elegantním, rekurzivní způsobem. Ale i když ne, rekurze je opravdu mocný nástroj nicméně. A tak je to určitě něco, dostat hlavu kolem, protože budete moci vytvořit docela v pohodě programy pomocí rekurze které by jinak mohly být složité psát pokud používáte smyčky a iterace. Jsem Doug Lloyd. To je CS50.