ZAMYLA: Abychom pochopili, rekurze, musíte nejprve pochopit rekurzi. S rekurzi v návrhu programu prostřednictvím že máte sebereferenční definice. Rekurzivní datové struktury, například, jsou datové struktury, které zahrnují se do jejich definice. Ale dnes, budeme se soustředit na rekurzivních funkcí. 

Připomeňme, že funkce se vstupy, argumenty a vrátí hodnotu jako jejich Výstup zastoupené Tento diagram zde. Budeme přemýšlet z krabice jako orgán funkce, která obsahuje soubor pokyny, které interpretují vstup a poskytovat výstup. Při bližším pohledu uvnitř těla funkce může odhalit volání další funkce stejně. Vezměte si tuto jednoduchou funkci, foo, že trvá jeden řetězec jako vstup a vytiskne, kolik písmen že řetězec má. Funkce strlen, pro délku řetězce, se nazývá, jehož výstup je potřebné pro volání printf. 

A teď, co je rekurzivní funkce Zvláštní je, že volá sama sebe. Můžeme reprezentovat tuto rekurzivní volání s touto oranžovou šipkou looping zpět k sobě. Ale pouze se znovu spuštěním bude provést další rekurzivní volání, a další a další. Ale rekurzivní funkce nemůže být nekonečný. Musí skončit nějakým způsobem, nebo vaše Program poběží navždy. 

Takže musíme najít způsob, jak zlomit z rekurzivních volání. Říkáme tomu referenční případ. Je-li splněna základní podmínka případ, Funkce vrací, aniž by další rekurzivní volání. Vezměte si tuto funkci, hi, funkci void že trvá int n jako vstup. Referenční případ nastane dříve. Pokud n je menší než nula, tisk bye a návrat Ve všech ostatních případech, Funkce vytiskne hi a provést rekurzivní volání. Další volání funkce hi se sníží vstupní hodnota. 

Nyní, i když jsme vytisknout hi, funkce se neukončí, dokud se vrátí jeho návratový typ, v tomto případě prázdnotě. Takže pro každé n jiné než základní věci, tato funkce hi vrátí hi n minus 1. Protože tato funkce je neplatné i když jsme nebude výslovně napište sem vracet. Budeme jen spustit funkci. Takže volání hi (3) bude tisknout hi a spustit hi (2), který vykonává hi (1) jeden který vykonává hi (0), kde referenční případ, podmínka je splněna. Takže ahoj (0) vytiskne bye a vrátí se. 

OK. Takže teď, že jsme pochopili základy rekurzivní funkce, které potřebují alespoň jeden referenční případ, jakož i rekurzivní volání, pojďme se přesunout na více smysluplné příklad. Jeden, který není jen návrat ztrátu bez ohledu na to, co. 

Pojďme se podívat na faktoriálu Provoz používá nejčastěji v pravděpodobnostní výpočty. Faktoriál n je součin každý kladné celé číslo menší než a rovná se n. Takže faktoriál pět je 5 krát 4 krát 3 krát 2 krát 1, čímž se získá 120. Čtyři faktoriál je 4 krát 3 krát 2 krát 1 za vzniku 24. A platí stejné pravidlo na jakékoli kladné číslo. 

Takže, jak můžeme napsat rekurzivní funkce, která vypočítá faktoriál z řady? No, budeme muset zjistit jak referenční případ, a rekurzivní volání. Rekurzivní volání bude stejný pro všechny případy s výjimkou základny případ, což znamená, že budeme muset najít model, který vám dá nám naše požadovaný výsledek. 

V tomto příkladu je vidět, jak 5 faktoriál zahrnuje násobení 4 na 3 o 2 o 1 A to samý násobení je zde, Definice 4. faktoriálu. Takže vidíme, že 5 faktoriál je jen 5 krát 4 faktoriál. Nyní se platí tento vzorec až 4 faktoriál i? Ano. Vidíme, že 4 faktoriál obsahuje násobení 3 krát 2 krát 1, velmi stejná definice jako 3 faktoriálu. Takže 4 faktoriál se rovná 4 krát 3 faktoriál, a tak dále a tak dále naše vzor tyčinky do 1 faktoriálu, který podle definice je roven 1. 

Neexistuje žádný další pozitivní vlevo celá čísla. Takže máme vzor pro naše rekurzivní volání. n faktoriál se rovná n krát faktoriál n minus 1. A náš základní scénář? Bude to jen naše definice 1 faktoriálu. 

Takže teď můžeme přejít k psaní kód funkce. Pro základní případ, budeme mít stav n se rovná rovná 1, kde vrátíme 1. Pak se pohybuje na rekurzivní volání, vrátíme n-krát faktoriál n minus 1. 

Nyní pojďme vyzkoušet tuto dotazy. Zkusme faktoriál 4. Na naší funkce je rovna se 4 krát faktoriál (3). Faktoriál (3) je rovna 3 krát faktoriál (2). Faktoriál (2) je rovna 2 krát faktoriál (1), která vrací 1. Faktoriál (2) se vrací 2 krát 1, 2. Faktoriál (3), mohou nyní vrátit 3 x 2, 6. A konečně, faktoriál (4) vrátí 4x 6, 24. 

Pokud jste narazila na problémy s rekurzivní volání, předstírat, že funkce pracuje již. Co tím chci říct je to, že byste měli věřit svým rekurzivní volání k návratu správné hodnoty. Například, když vím, že faktoriál (5) se rovná 5 krát faktoriál (4), budu věřit, že faktoriál (4) bude mi 24.. Ber to jako proměnnou, pokud bude, jako byste již definován faktoriál (4). Takže pro jakékoliv faktoriál (n), je to produkt z n a předchozí faktoriál. A to předchozí faktoriál se získá voláním faktoriál n minus 1. 

Teď uvidíme, jestli můžete implementovat rekurzivní funkce sami. Vložte svůj terminál, nebo run.cs50.net, a napsat funkci částku že má celočíselnou n a vrátí součet všech po sobě jdoucích pozitivní celá čísla od N do 1.. Napsal jsem z částky některých Hodnoty, které vám pomohou naše. Za prvé, zjistit, base case stav. Pak se podívejte na součtu (5). Můžete to vyjádřit v rámci jiné částky? A teď, co součet (4)? Jak můžete vyjádřit součet (4) , pokud jde o jiné částky? 

Jakmile budete mít součet (5) a součtem (4) vyjádřeno v jiné částky, viz pokud můžete identifikovat vzor pro součet (n). Pokud ne, zkuste několik dalších čísel a vyjádřit své částky v podmínky dalších čísel. Tím, že pozná vzory pro diskrétní čísla, jste na dobré cestě k identifikaci vzor pro libovolné n. 

Rekurze je opravdu mocný nástroj, tak samozřejmě, že to není omezeno na matematické funkce. Rekurze může být velmi efektivně využity pokud se jedná o stromy na instanci. Podívejte se na krátký na stromy pro důkladnější přezkum, ale pro tuto chvíli připomenout, že binární vyhledávací stromy, v zejména, jsou vyrobeny z uzlů, z nichž každý s hodnotou a dvou uzlů ukazatele. Obvykle to představuje nadřazený uzel má jeden řádek bodování do uzlu levé dítě a jeden na pravé podřízený uzel. Struktura binární vyhledávání strom půjčuje sebe dobře na rekurzivní vyhledávání. Rekurzivní volání buď projde levý nebo pravý uzel, ale více z toho stromu zkratu. 

Řekněme, že chcete provést operaci každý uzel v binárním stromu. Jak byste mohli jít na to? No, mohl bys napsat rekurzivní funkce, která provádí operace Na nadřazeného uzlu a je rekurzivní volat na stejnou funkci, procházející v levém a právo podřízené uzly. Například, tato funkce foo, že změní hodnotu daného uzlu a všechny své děti do 1. Referenční případ, z Null uzel příčin funkce vrátit, což znamená, , že zde nejsou žádné uzly odešel v tomto podstromu. 

Pojďme si projít to. První rodič je 13. Změníme hodnotu 1, a pak volat naše funkce na levé straně, jakož jako pravé. Funkce foo, se nazývá nalevo sub-tree první, tak levý uzel bude přidělen 1 a foo bude být volán na děti, které nodu, první vlevo a pak vpravo, a tak dále a tak dále. A řekněte jim, že pobočky nemají každá další děti, takže stejný proces bude pokračovat správným děti dokud uzly celého stromu jsou převelen k 1.. 

Jak můžete vidět, nejste omezeni jen jeden rekurzivní volání. Stejně jako mnoho, jak se dostat práci. Co kdyby jste měli na strom, kde každý Uzel měl tři děti, Levá, střední a pravá? Jak byste upravit foo? No, jednoduše. Stačí přidat další rekurzivní volání a předat ukazatel na střed uzlu. 

Rekurze je velmi silný, a ne zmínit, elegantní, ale to může být obtížné koncept na první, tak se pacienta a vzít si na čas. Začněte se základním případu. Je to obvykle nejjednodušší určit, a pak můžete pracovat zpět odtamtud. Víte, že je třeba dosáhnout svého referenční případ, takže síla vám několik rad. Pokuste se vyjádřit jeden konkrétní případ podmínky ostatních případech, nebo v dílčích sadách. 

Díky za sledování této krátké. Přinejmenším, nyní můžete pochopit, vtipy, jako je tento. Jmenuji se Zamyla, a to je CS50. 

Vezměte si tuto funkci, hi, void funkce, která vezme int, n, jako vstup. Referenční případ nastane dříve. Pokud n je menší než 0, tisk "Na shledanou" a návrat.