Pojasnjenje oko rekurzije

Pojasnjenje oko rekurzije

offline
  • Més que un club
  • Glavni vokal @ Harpun
  • Pridružio: 27 Feb 2009
  • Poruke: 3898
  • Gde živiš: Novi Sad,Klisa

Imam zadatak da odredim N-ti clan fibonacijevog niza preko rekurzije. Uz pomoc Google-a sam nasao resenje, ali mi to bas i nije od koristi kada kod ne razumem

#include <stdio.h> int Fibonaci(int n) {    if ((n == 1) || (n == 2))       return 1;        return Fibonaci(n-2) + Fibonaci(n-1); }

ovo je kod same funkcije za pronalazenje n-tog clana fibonacijevog niza. Mene zanima kako to u okviru jednog returna imamo dve funkcije? Jel program izvrsava dve funkcije istovremeno (pa onda 4 pa tako dalje..) Rekurzija (pored lista) mi je ubedljivo najslabija karika sto se poznavanja C-a tice, tako da svako pojasnjenje bi mi puno znacilo Smile



Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.
offline
  • Pridružio: 04 Jul 2011
  • Poruke: 5424

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. Smile


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. :



offline
  • Fil  Male
  • Legendarni građanin
  • Pridružio: 11 Jun 2009
  • Poruke: 16586

Malo o rekurziji i Fibonacijevom nizu imas ovde:
http://www.mycity.rs/C/1-Uvod-u-C.html

Ko je trenutno na forumu
 

Ukupno su 1300 korisnika na forumu :: 35 registrovanih, 9 sakrivenih i 1256 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 3466 - dana 01 Jun 2021 17:07

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: ajo baba, Areal84, Asparagus, bladesu, BORUTUS, debeli, Dimitrise93, Dorcolac, DPera, draganl, dushan, Georgius, hyla, ikan, jackreacher011011, Karla, kihot, kovinacc, kuntalo, ljuba, mgolub, Mi lao shu, MikeHammer, milenko crazy north, Milometer, MilosKop, Miroljub1979, Mixelotti, nemkea71, nextyamb, shone34, vasa.93, vathra, W123, zlaya011