|
Predpostavljam da znaš da je rekurzija u stvari pozivanje funkcije iz nje same, sa uslovom za kraj rekurzije.
Za nalaženje N-tog broja pozivamo funkciju Fibonaci(n). Ako je N=1 ili N=2:
if ((n == 1) || (n == 2))
return 1;
Ovaj deo kod a je uslov za prekid rekurzije. Tj. Prvi i drugi član Fibonačijevog nia su 1 i 1.
Ako je N>2 onda funkcija poziva samu sebe, i zo za N-1 i N-2, to proizilazi iz toga da nam je A[n]=A[n-1]+A[n-2]. Tj. N-ti element fibonačijevog niza (obeležio sam ga sa A) jednak je zbiru prethodna 2, a to su elementi na pozicijama n-1 i n-2.
return Fibonaci(n-2) + Fibonaci(n-1);
Evo primera kako funkcioniše rekurzija.
Tražimo 6-ti element fibonačijevog niza. Znači n=6:
Pozivamo funkciju Fibonaci(6). Pitamo da li je n>2, jeste. Ulazimo u return i tu dobijamo da je:
fibonaci(6)=fibonaci(5)+fibonaci(4).
Sada nam je potrebno da izračunamo koliko je fibonaci(5), odnosno fibonaci(4).
Isto ponavljamo za oba pozivanja.
Prvo fibonaci(5). Ispitujemo da li je veci od 2, jeste. Ulazimo u return i imamo da je:
fibonaci(5)=fibonaci(4)+fibonaci(3).
Analogno tome fibonaci(4)=fibonaci(3)+fibonaci(2).
Zatim racunamo fibonaci(3), istim postupkom kao gore dobijemo da je
fibonaci(3)=fibonaci(2)+fibonaci(1)
U principu, funkcija bi ponovo pozvala i fibonaci(4) pored ovog fibonaci(3), ali to se naziva preklapanje (već smo to računali), i dovodi samo do usporavanja programa.
Ostalo je još za argument 2, ali on neće stići dalje od IF-a. Isto i za argument 1
Nakon toga se rekurzija vraća unazad, i računa nam sve elemente do N-1 (uključujući). Kada izračuna N-1 i N-2 elemente, sabraće ih i ti ćeš dobiti rešenje.
Pitaj ako ti neki deo nije jasan. 
Možda ti je ovo zbunujuće, ali rekurziju ćeš najbolje shvatiti kroz primere, uzmi papir i olovku i zapisuj šta ti ta funkcija radi korak po korak. Videću da potražim, imao sam neke knjige vezane za rekurziju. :
|
