Tip:
Highlight text to annotate it
X
U ovom snimku bih hteo da
se osiguram da zaista razumemo šta se dešava
kada pozovemo naše rekurzivne Fibonačijeve funkcije.
Dakle, pretpostaviću da neko poziva funkciju sa
argumentom, i da prosleđuju 5 kao argument.
Ne bih da izaberem prevelik broj za argument,
jer bih onda morao da vam je objašnjavam 100 godina.
Pa hajde da probamo fibonacci(5).
Dakle, u ovoj situaciji, u kontekstu ove funkcije
parametar n će biti jednak 5.
Dakle, u našem prvom prolazu, parametar n će biti jednak 5.
I, kako smo napisali,
rekli smo da, ako je *n < 2* funkcija vraća n.
5 definitivno nije manje od 2,
tako da ćemo otići do else dela if uslova
ili else uslova i vratiti vrednost
fibonacci od (n-1) plus fibonnacci od (n-2)
Tako da, kad ovo pozovem, na kraju će se svesti na...
ako želite da razmišljate na takav način, ili pojednostavljeno,
vratiće ono što će biti ista stvar kao fibonacci od...
setite se da je n bilo 5
dakle n-1 je 4
plus fibonacci od n-2, što je, pošto je n bilo jednako 5 kad smo pozvali funkciju,
dakle 5-2 je 3.
Pa, ovo su opet novi pozivi funkcije,
tako da ćemo da prođemo kroz nju opet -
n nije 5, nego 4 i 3.
Hajde onda ovo da isprobamo.
Dakle, ovde je n jednako 4...
n je jednako 4.
Tako da opet 4 nije jednako 2,
tako da ćemo ovaj deo preskočiti
i idemo do else.
Onda vraćamo fibonacci(4-1) što je jednako 3.
Onda će se ovo pojednostaviti na
- ili bolje da kažem svesti na -
fibonnacci od 4-1 što je 3
plus fibonacci od 4-2
što je fibonacci od 2,
tako da ćemo ovde mi u suštini vratiti ovo,
a ovde desno ćemo vratiti fibonacci od 3.
Sad ću ovo da nacrtam, pošto će se uskoro zapetljati.
Znači, ovo vraća ovo ovde ljubičasto,
a ovo ovde što sam podvukao zelenim će vratiti...
n je sada 3; 3 nije manje od 2,
pa idemo ovamo
i vratiće fibonacci od 3-1 što je fibonacci(2)
i plus fibonacci od 3-2, što je fibonacci(1)
i onda ćemo da odemo ovamo
i moraćemo da izračunamo svaku od ovih stvari
i ovo su samo novi pozivi fibonacci funkcije
i fibonacci(3), tako da možete da vidite kako se ovo sada već prilično komplikuje.
Počeću da pišem "fib" kao skraćenicu za fibonacci
da mi ne nestane prostora.
Fibonacci(3) kad pozovemo
n, 3 nije manje od 2,
svede se na fibonacci(3-1).
Napisaću samo fib, skraćeno od fibonacci.
Fibonacci od 2 plus fibonacci od (3-2)
plus fibonacci od 1,
tako da se to sad svede na to,
a ovde fibonacci od 2,
2 nije manje od 2,
tako da ćemo morati da vratimo fibonacci od 2-1.
To je, dakle, fibonacci od 1 plus fibonacci od 2-2,
pa plus fibonacci od 0
tako da se svodi na ta dva poziva fibonacci funkcije,
a ovamo je kod fibonacci(2) ista stvar.
Pozvali smo fibonacci(2).
To će da se uprosti baš kao onaj fibonacci(2).
Svešće se na poziv
fibonacci(1) i fibonacci(0).
I onda imamo fibonacci od 1 -
ovo je interesantno.
Pošto kad je n jednako 1
ovaj uslov ovde odjednom postaje bitan.
Pošto je n manje od 2 i kaže vrati vrednost n,
tako da će ovo, baš ovo ovde, pojednostaviti
ovaj izraz ovde i on će se svesti na 1 -
ta vrednost će biti 1.
I onda pogledamo sve ove ovamo:
fibonacci(2); znamo da fibonacci(2) rezultira sa fib(1) + fib(0).
To ću ovde i da napišem,
tako da ovde imamo fibonacci(1) plus fibonacci(0).
Fib je skraćeno od fibonacci.
I onda znamo fibonacci od 1 -
1 je manje od 2, tako da vraćamo n,
tako da će ovo da vrati 1.
Fibonacci od 1 samo vraća 1.
Fibonacci od 0,
a 0 je manje od 2, vraća 0.
Tako da fibonacci(0) samo vraća 0.
Fibonacci od 0 vraća 0.
Fibonacci od 1 vraća 1
Fibonacci od 0 vraća 0.
A onda fibonacci od 1 vraća 1.
Fibonacci od 0 vraća 0.
Tako da sve vreme interpreter obrađuje ovaj rekurzivni poziv funkcije
i na neki način mora da zapamti i sve prethodne, da zna kako je došao dotle gde je trenutno,
pošto kada ne kraju dođe do osnovnih slučajeva,
kada dođe do toga da je n jednako 1 ili 0,
on u stvari dobija čisto numerički odgovor.
On onda mora da ide gore do svog prethodnog odgovora.
Tako da je fibonacci(2) ovde
jednako 1+0.
Fibonacci od 2 će da se pojednostavi na 1.
Ovo fibonacci(3) je fibonacci(2) + fibonacci(1).
Oni se svode na 1,
tako da će ovo da bude 1+1,
tako da će ovo da bude 2.
Idemo ovamo, fibonacci od 2,
fibonacci(1) + fibonacci(0) = 1,
fibonacci(2),
1+0 je 1.
Idemo na fibonacci od 1, ovo je 1.
I onda idemo gore na ovaj nivo.
Na neki način mi se vraćamo nazad sve dok ne dođemo do prvobitnog poziva funkcije.
I ja sad neću ulaziti u detalje
toga kako interpreter to u stvari radi,
iako je to u stvari zaista fascinantna stvar,
nego ću samo da rasmišljam o tome kako mi razmišljamo o tome šta se tu dešava
u toku ovog rekurzivnog pozivanja funkcije, i zašto, zašto ovo funkcioniše,
zašto nam daje ispravan odgovor.
I onda idemo ovamo na fibonacci(4).
Pa, fibonacci(4), četvrti Fibonačijev element,
je zbir trećeg i drugog Fibonačijevog elementa
koje smo već shvatili -
oni su 2 i 1, samo uzmemo njihov zbir i dobijemo 3.
Treći Fibonačijev element, po definiciji Fibonačijevog niza,
je zbir prvog i drugog elementa.
Svaki od njih je jedan.
Zbir jedan plus jedan je dva.
Peti element, peti Fibonačijev broj,
peti Fibonačijev element,
je zbir četvrtog i trećeg elementa.
Oni su tri i dva,
Tako da je tri plus dva jednako pet.
Tako da će ovo ovde da se svede na 5.
Nadam se da to sad malo razjašnjava
kako ovaj rekurzivni program u stvari radi.
Šta je dobro u ovome je
da stvar ne bi funkcionisala da nismo otišli dole i definisali
osnovne slučajeve fibonacci(1) i fibonacci(0).
Samo bi pozivala sebe zauvek, i nikad nigde ne bi stigla.
I ono što je ključ kod rekurzivnih funkcija jeste to što može da poziva sebe,
dokle god pri svakom pozivu sebe
ona napreduje prema osnovnim slučajevima.
Tako da će u jednom trenutku,
ako nastavi da poziva samu sebe, poziva samu sebe,
ona na kraju moći da dođe tim pozivima
skroz do osnovnih slučajeva,
i da onda iz svega toga rekonstruiše šta je prvobitna tražena vrednost.
i to je zašto ona funkcioniše -
svaki poziv fibonacci funkcije je jednostavnija verzija.
Imam malo n
i pre ili kasnije svako moje n će da dođe do osnovnih slučajeva,
što će mi dati prave brojne vrednosti
koje onda mogu da koristim u našim prvobitnim pozivima funkcije.
Nadam se da to malo pomaže.
Rekurzija može da bude malo zbunjujuća,
ali u isto vreme
može da bude elegantna i lepa na svoj način.