Programování v Pythonu
Programování v Pythonu (13/21) · 5:35

Rekurzivní funkce faktoriál Úvod do rekurzivních funkcí.

V tomto videu bych Vám rád představil věc, o níž si myslím, že je jednou z nejlepších myšlenek ve světě počítačů a tou je rekurze. Takže způsob jakým definujeme funkci na výpočet faktoriálu v předchozích dvou videích je vlastně iterativní definice. Iterujeme přes rozdílné hodnoty proměnné "i" a potom v podstatě bereme tyto hodnoty a přičítáme k nim 1, potom takto vzniklým číslem násobíme dosavadní součin - "product". A když budeme iterovat přes všechna tato čísla náš konečný součin bude mít postupně všechny hodnoty, které vzniknou násobením i a dosavadního součinu a tyto všechny jsou uloženy v proměnné "product". Teď se budu snažit přepsat tento program. Co je vlastně "cool" na funkcích? Přepíšu tuto funkci. Na funkcích je "cool" to, že... Tato funkce vlastně říká: "Tady ti vracím faktoriál daného čísla". Vůbec nás nezajímá, jak je funkce vlastně napsaná. A tak, cokoliv, co používá tuto funkci, bez ohledu na to, jak jsem funkci napsal, pokud je napsána správně, zbytek kódu se o to, jak je napsána, nemusí starat Pokud jsem napsal, co je uvnitř funkce, vnitřnosti této funkce, správně, i když to udělám úplně jinak, němělo by to ovlivnit chování žádné další funkce, která bude moji funkci volat. Pojďme se podívat dále a zkusme si definovat tuto funkci rekurzivně. A myslím, že toto pro nás bude celkem zajímavé. Takže teď budu funkci tvořit poněkud odlišně. Přidáme sem taky nějaké podmínky, takže řekl bych... Svým způsobem je rekurze skutečně hluboká a komplikovaná myšlenka a v některých ohledech je to jednodušší než cokoliv jiného. Posunu teď tento kód trochu níž... Co chci říct: "Hele, pokud číslo..." Vždy se budeme snažit myslet na základní případ. Jak vypadá situace, když se snažíme dostat nejmenší hodnoty do čísla, které nám dají nějakou rozumnou odpověď? Tak řekneme: "Hele." Pokud číslo je menší nebo rovno 1. Takže pokud je menší nebo rovno 1, vrátíme hodnotu, potom jeho faktoriál bude... vrátíme hodnotu 1. Jako byste chtěli stejné chování, jaké měla stará funkce. Stará funkce, bez ohledu na to, jestli jsme vložili 1 nebo 0, vlastně můžeme dát funkci i číslo -1 nebo -2 a vždy nám vrátí faktoriál rovný 1. A to je přesně to, co tu děláme. Vracíme 1, pokud je číslo menší než 1. A toto taky definuje náš základní případ. Dokonce ho tu můžu označit Toto je náš základní případ - "base case". A uvidíte za chvíli, co si představuju pod pojmem základní případ. A toto je, co teď budu dělat, toto je opravdu zajímavá část týkající se rekurze. Pokud není číslo menší nebo rovno 1, tak můžeme napsat "elif", vlastně spíš teď napíšu "else". Takže pokud číslo není menší nebo rovno 1, budeme vracet nějakou jinou hodnotu. A co budeme vracet je toto číslo násobeno faktoriálem čísla o jedna menším. Voláním funkce "factorial()". Teď, důvod toho, proč je to tak cool a zajímavé a všechno, je že jsem vlastně definoval "něco", co to "něco" používá. Takže jsem právě definoval funkci nazvanou "factorial" a definoval jsem to použitím definice funkce faktoriál. Odkazuje sama na sebe. To je podstata rekurzivních funkcí. Ale pokud se nad tím zamyslíte, a zkusím to znázornit podrobněji v následujícím videu, aby to šlo lépe pochopit, mělo by to fungovat nějak takto, protože, pokud dáte funkci 1 nebo 0 jako vstupní číslo vrátí funkce právě 1. Co se stane, pokud předáte funkci číslo 2? No, pokud číslo je 2, program vlastně řekne: "Hele, číslo je menší než , tak já půjdu sem." Takže program říká: "Vrátím hodnotu rovnou 2 x funkce factorial(2-1)." nebo "factorial(1)" Potom se zavolá funkce "factorial()" znovu a "factorial(1)" je jednoduše 1. Takže mi funkce vrátí 2 krát 1. Takže to bude fungovat pro 2. Zkusme to pro 3. Pokud budete počítat faktoriál 3, spadne to do této části programu, protože 3 není menší nebo rovno 1, a funkce vrátí 3 krát "factorial(3-1)", což je 2, takže "factorial(2)". A víme, že nám funkce vrátí správnou odpověď pro "factorial(2)", takže to vrátí 3 krát 2, což je 6, což je faktoriál čísla 3. Tak jste doufám pobrali tu základní myšlenku. Spočtení faktoriálu čísla 4 bude fungovat z toho samého důvodu. Program sestupně vrátí 4 krát výsledek funkce "factorial(3)". Víme, že program funguje pro faktoriál 3. A jenom, abychom dokázali, že tu neděláme nějaké bláznivé voodoo, a že toto bude ve skutečnosti fungovat, zkusme spustit program. Pusťme si teď program. Toto jsou nějaké věci, co jsem dělal dřív, smažu je. Spusťme tedy program. Takže, všechno, co jsem udělal je, že jsem předefinoval funkci "factorial()", ale předefinoval jsem ji rekurzivně. Nechci tu měnit komentáře, takže to teď uložím a spustím, pokusme se zjistit, co program dělá, Spusťme program a podívejme se, jestli dělá, co potřebujeme, aby dělal. Super. Teď to po nás chce nějakou vstupní hodnotu, dejme tomu, že nás zajímá faktoriál čísla 5. 120. Takže, ještě jednou, náš program na výpočet faktoriálu, bez ohledu na to, co mu dáme jako vstupní hodnotu, nám dává správnou odpověď. Ale co je fakt cool, je skutečnost, že teď to dělá rekurzivně. Když zkusíme zjistit faktoriál čísla 6. řekneme:"Ok, faktoriál čísla 6." Je 6 méně nebo rovno 1? Není. Takže to spadne do této "else" větve. No a pak to říká: Vrať na výstupu hodnotu 6 krát "factorial(5)". Dobře, zapamatujeme si, 6 krát faktoriál čísla 5 byl... Zapomněl jsem, co byl faktoriál čísla 5! Faktoriál čísla 5 bude 5 krát faktoriál čísla 4. A tak dále, potom faktoriál čísla 4 je 4 krát faktoriál čísla 3, postupně až k faktoriálu čísla 1, což je 1. A tak, nakonec vlastně vrátíme hodnotu 6 krát 5 krát 4 krát 3 krát 2 krát 1.
video