>> 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.