Tip:
Highlight text to annotate it
X
V tomto videu se chci ujistit, že opravdu chápeme co se děje,
když zavoláme rekurzivní Fibonacciho funkci.
Zde předpokládám, že ji někdo zavolá
s argumentem, který je roven číslu 5.
Nechci vybrat velké číslo, protože bych to vysvětloval dlouho.
Zkusme fibonacci(5).
V této situaci, v kontextu této funkce,
je zde parametr 'n' roven 5,
takže v prvním průchodu bude parametr 'n' roven 5.
Funkci jsme napsali tak, že pokud n < 2, pak vrátíme 'n'.
5 určitě není menší než 2,
takže budeme pokračovat "else" částí podmínky,
Řekneme vrať Fibonacciho hodnotu pro 'n - 1' plus Fibonacciho hodnotu pro 'n mínus 2'.
Když toto zavoláme, bude to nakonec redukováno,
nebo jinak řečeno zjednodušeno,
a vrátí stejnou hodnotu, jako je hodnota Fibonacciho funkce pro
původní 'n', které bylo 5
Takže 'n' mínus 1 je 4
plus Fibonacciho hodnota pro 'n - 2', 'n' bylo při spuštění funkce 5,
takže 5 mínus 2 je 3.
Toto jsou pouze další volání funkcí,
takže budeme postupovat stejně jako minule.
n nyní není 5, ale 4 a 3.
Pojďme to zkusit.
Tady je 'n' rovno 4.
'n' je rovno 4.
A opět 4 není menší než 2,
takže tuto část provádět nebudeme.
Půjdeme else větví,
vrátíme fibonacci(4 mínus 1) což je 3,
to bude zjednodušeno
nebo respektive rozděleno
na Fibonacciho hodnotu pro 4 mínus 1, což je 3
plus Fibonacciho hodnota pro 4 mínus 2
tedy Fibonacciho hodnotu pro číslo 2.
tedy tady tohle vrátí toto
a zde na pravé straně Fibonacciho hodnota pro 3...
Nakreslím to, protože se to brzy určitě pomíchá.
Toto tedy vrátí to co je v purpurové barvě
a zároveň to co je podtrženo zelenou,
'n' je nyní 3, 3 není menší než 2,
takže půjdeme sem
a to vrátí Fibonacciho hodnotu pro 3 mínus 1, tedy fibonacci(2),
plus Fibonacciho hodnotu pro 3 mínus 2, tedy fibonacci(1),
a nyní se přesuneme sem
a vyčíslíme každé z těchto volání.
Jsou to pouze další volání Fibonacciho funkce
fibonacci(3), můžete vidět jak se to stále opakuje
začnu psát zkratku fib pro fibonacci
abychom se tak neunavili.
Když zavoláte fibonacc(3),
tak n=3, což není menší než 2
to se zjednoduší na fibonacci(3 mínus 1).
Napíšu fib pro fibonacci.
fibonacci(2) plus fibonacci(3 mínus 2)
plus fibonacci(1)
to se zjednoduší nebo rozdělí na toto
tady je Fibonacciho hodnota pro 2.
2 není menší než 2,
takže vrátíme Fibonacciho hodnotu pro 2 mínus 1
fibonacci(1) plus fibonacci(2 mínus 2),
tedy fibonacci(0).
Toto se tedy rozdělí na tyto dvě volání
a u fibonacci(2) se jedná uplně o to samé.
Voláme fibonacci(2),
to se rozdělí uplně stejně jako fibonacci(2) před chvílí.
Rozdělí se to na volání
fibonacci(1) a fibonacci(0).
Pak tady máme Fibonacciho hodnotu pro 1.
Tohle je zajímavé,
protože když 'n' je rovno 1
tato podmínka najednou začne být důležitá,
protože 'n' je menší než 2, a říká ať vrátíme 'n'
takže toto se zjednoduší.
Toto volání se zjednoduší na 1.
Vyhodnotí se na 1.
Pak se podíváme na další volání
Víme, že fibonacci(2) se rozdělí na fib(1) plus fib(0).
Rozepíši to tady.
Takže fibonacci(1) plus fibonacci(0),
fib je zkratka pro fibonacci,
Fibonacciho hodnotu pro 1 již víme.
1 je méně než 2, tedy vrátíme 'n'.
Tohle tedy vrátí 1.
Fibonacci(1) vrátí 1
Fibonacciho hodnota pro 0
0 je menší než 2, vrátíme 0.
takže fibonacci(0) vrátí 0.
fibonacci(0) vrátí 0,
fibonacci(1) vrátí 1,
fibonacci(0) vrátí 0,
a fibonacci(1) vrátí 1.
fibonacci(0) vrátí 0.
Celou dobu interpret zpracovává toto rekurzivní volání,
musí si zapamatovat všechny předešlé volání,
protože jakmile se při vyhodnocení dostane na nejnižší úroveň
kde n je rovno 1 nebo 0,
funkce vrátí číselnou hodnotu,
a pak se to musí zpětně sestavit do předešlého stavu
tedy fibonacci(2)
je 1 + 0.
fibonacci(2) se zjednoduší na 1.
fibonacci(3) je fibonacci(2) plus fibonacci(1).
toto zjednodušíme na 1.
Tento výraz bude 1 + 1,
tedy 2
Přesuňme se k fibonacci(2).
fibbonacci(1) + fibbonacci(0) = 1
fibbonacci(2)
1 plus 0 je 1.
Přesuneme se k fibonacci(1), to je 1.
Poté se přesune o úroveň nahoru.
Posunujeme se nyní opačným směrem zpátky k původnímu volání.
Nebudu detailně vysvětlovat,
jak to interpret ve skutečnosti dělá,
protože to je celkem zajímavá diskuze.
Budeme jen přemýšlet o tom, co se dějě
během zanořování funkčních volání a proč to funguje.
Proč to vrátí správnou odpověď?
Přesuňme se k fibonacci(4).
fibonacci(4), čtvrtá Fibonacciho hodnota,
je součtem třetí a druhé Fibonacciho hodnoty,
na které jsme již přišli.
Jedná se o 2 a 1, jejich součtem je 3.
Třetí Fibonacciho hodnota dle definice Fibonacciho řady,
je součtem první a druhé Fibonacciho hodnoty,
které jsou obě 1,
součet 1 plus 1 je 2.
Páté číslo ve Fibonacciho řadě...
Páté číslo ve Fibonacciho řadě
je součtem čtvrtého a třetího Fibonacciho čísla,
tedy 3 a 2,
takže 3 plus 2 je 5.
Tohle se vyhodnotí na 5.
Doufám, že to alespoň trochu vyjasňuje,
jak rekurzivní program ve skutečnosti funguje.
Co je na tom skvělé je to,
že to nebude fungovat pokud nebudou definovány
hraniční hodnoty pro fibonacci(1) a fibonacci(0).
Protože by to volalo stále sebe sama a nikam by se to nedostalo
a proto klíčem rekurze je, že volá sebe sama
tak dlouho
dokud se nedostane k základním případům.
V určitém okamžiku,
pokud volá pořád sebe sama,
bude schopna vytvořit tyto volání zpětně,
aby se dostala k původnímu volání
a vyhodnotit jaká byla původní hodnota,
a právě proto to funguje.
Každé volání Fibonacciho funkce je zjednodušenou verzí.
Dostaneme zmenšené 'n'
a nakonec 'n' se dostane na základní případ,
kde dostaneme skutečné hodnoty,
které pak můžou zpětně zrekonstruovat původní volání.
Doufám, že to pomohlo.
Rekurze může být matoucí,
ale také
může být svým způsobem elegantní a krásná.