Programování v Pythonu
Programování v Pythonu (16/21) · 7:37

Fibonacciho rekurzivní funkce Užití rekurze pro napsání Fibonacciho funkce

jestliže jste ještě nezkoušeli si napsat vlastní rekurzivní funkci Fibonacciho posloupnosti, tak bych vám opravdu doporučil, alespoň se o to pokusit. Opravdu to zkuste, než se podíváte na toto video. Jestliže jste to udělali, nebo jste líní, myslím, že se můžete podívat na toto video. Pokusíme se napsat Fibonacciho funkci podle specifikací které jsem zadal, když jsem se poprvé pokoušel napsat Fibonacciho funkci. Nazvěme tuto funkci opět fibonacci, fi-bo-na-cci fibonacci, má to zde parametr n, ten bude předávat argument abychom mohli říct, který člen Fibonacciho posloupnosti chceme. Ale nyní to uděláme rekurzivně a uvidíme, že je velice intuitivní napsat Fibonacci funkci rekurzivně, je to téměř magie, a později uvidíme, že to není nutně nejefektivnější způsob jak napsat Fibonacciho funkci. Vždy když píšeme rekurzivní funkci, musíme hodně přemýšlet o základních případech. Dobře, základní případy Fibonacciho posloupnosti. Máme dva základní případy. je zde nultý člen a první člen a ty jsou dány definicí takže řekněme jestliže chceme nultý člen když n rovná se nula když n rovná se nula to znamená, že chceme nultý člen a nultá\ý člen je ve skutečnosti nula! A můžeme říct jinak když, jinak když n rovná se jedné, n rovná se jedné, pak, pak můžeme vrátit pak můžeme vrátit pak můžeme vrátit jedničku! Nultý člen je nula, první člen ve Fibonacciho posloupnosti je jedna A tady je to, kde se děje trocha magie. jinak, jinak vrať -a toto je velmi cool- vrať Fibonacci. Fib-o-na-cci s parametrem n mínus jedna, takže nezáleží na tom, jaký je předchozí člen Fibonacciho posloupnosti, plus Fibonacci, plus Fibonacci s parametrem n mínus dva. Myslím, že toto by mělo fungovat, a to je to, proč to vypadá jako magie. Protože vše co říkáme je, když jchcete nultý člen, je to nula když chcema první člen,je to jedna - dáme sem nějaké mezery- Když chcema první člen, je to jednička. A když chceme jiný člen, -když chceme jakýkoliv jiný člen- takže jinak, když chceme - toto je jinak když- když žádný z těchto není pravdivý, takže ani nula ani jedna, když to je nějaké jiné číslo, bude to Předpokládáme, že na vstuopu je nějaké ne negativní celé číslo tady toto se zastaví, když bychom sem dali nějaké nezáporné číslo do nezáporného, tedy záporného členu Předpokládejme, že máme, nezáporné celé číslo, a pak řekneme podívej! Když to není nultý člen ani první člen, tak prostě vem Fibonacciho s argumentm o jedna menším než je aktuální argument plus fibonacci s argumentem o dva menším než je aktuální, a mlžeme to zkusit, například: Vezměme si Fibonacciho dvou. n není nula, takže neuděláme toto n není jedna, takže neuděláme toto, ake řekneme vrať Fibonacci (dva minus jedna) což je Fibonacci 1 plus Fibonacci (dva minus dva), plus Fibonacci 0. Ale my známe Fibonacci 1, to je jedna Fibonacci 0 se vyhodnotí jako nula. takže to bude jedna plus nula neboli, jen jedna A pokračujeme! Zkuste Fibonacci 3! a bude to fungovat! protože víme, že Fibonacci nuly, jedné nebo dvou fungueje, protože Fibonacci 3 se rozloží na Fibonacci 2 plus Fibonacci 1. Víme, že Fibonacci 2 je jedna, a Fibonacci 1 je 1 jedna plus jedna je dva. takže pokračujeme v práci. Nyní můžeme zkusit, jen to uložím, uložím soubor jako rekurzivní Fibonacci . rekurzivní Fibonacci , rekurzivní Fibonacci . nyní spustíme program. Toto definuje funkci, v mém prostředí, ještě musím zavolat funkci. Spustíme to, a zavoláme funkci Fibonacci 4. Dá mi to správnou odpověď. Fibonacci 10! padesát pět, správná odpověď. Fibonacci, můžeme zkusit jednoduché věci, Fibonacci nuly, nultího členu je nula. Takže to funguje. Toto je důvod, proč je rekurze tak trochu magická. Jestliže to chceme ještě více zjednodušit, můžeme si říct, že nultý člen Fibonacciho posloupnosti je nula první člen Fibonacciho posloupnosti je jedna Takže když se ptáme na nultý nebo první člen, je to stejné jako to číslo. Takže to můžeme trochu zjednodušit Když předpokládáme, že někto vloží nezáporné celé číslo, mlůžeme říct něco jako že když n, když n rovná se nule, nebo n rovná se jedné nebo n rovná se jedné, vrať, vrať n! Podívejme se, jestli to funguje. Podívejme se, jestli to trochu zjednodušilo náš kód. Zkusíme toto, uložíme to, spustíme, spustíme, a nyní zkusíme Fibonacci , Fibonacci deset a stále to funguje! Opravdu, nultý člen je nula a první člen je jedna, to funguje. Nebo to můžeme ještě více zjednodušit. Když n je menší než dva, tak by také mělo fungovat, protože když to je nula nebo jedna, vracíme n, jinak se vrátíme a orivedeme toto. Zkusme to. Spustíme to a zkusíme Fibonacci 10. Zdá se, že počítač je schopný to vypočítat., velmi rychle, a tak, ale když chceme vidět všechnu práci co dělá, všechna volání Fibonacciho, můžeme to udělat tak, že napíšeme vypiš sem, takže pokaždé když se Fibonacci dostane k příkazu vytiskni, vypíše text "fibonacci:" a pak přidáme k tomu řetězci text aktuální argument. Takže argument tohoto bude n, a chci mít jistotu, že se to zobrazí jako řetězec takže to dám do řetězce. Toto je v podstatě jen to, že vezmeme číslo a ujistíme se, že to je ´bráno jako řetězec, a když to přidáme k tomutu řetězci, vytvoří to jeden velký řetězec. Pdívejme se, co toto dělá. Zkusíme to nejrve s menšími hodnotami. Nadefinovali jsme funkci, Fibonacci uděláme Fibonacciho tří. povšimněte si když to zavolá Fibonacciho tří, aby udělal Fibonacciho tří, musí zavolat Fibonacciho dvou a Fibonacciho jedné, a aby udělal Fibonacciho dvou, musí zavolat Fibonaccihoho nuly a Fibonacciho jedné. Takže musí provést všechna tato volání Fibonacciho, jen aby spočítal hodnotu Fibonacciho tří. A pak mi to dá odpověď. Jesstliže děláme Fibonacciho deseti, bude to opravdu bláznicé, takže já udělám, udělám Fibonacciho šesti. Uvidíme, kolik zavolání Fibonacciho to musí udělat. Musí to udělat všechna tato zavolání Fibonacciho, Je to velmi výpočetně složítá věc. Ale počítač je velmi rychlý, takže to nepoznáme. V budoucnu bude mluvit o tom, jak přemýšlíme o tom, jaká výpočetní složitost, v závislosti na různých způsobech implementace funkce, jamůže být.
video