Ova funkcija "zna" da je faktorijel od 1 (ili manjeg broja) 1 i da je faktorijel nekog broja proizvod tog broja i "prethodnog faktorijela".
Ako tražiš faktorijel od 5, funkcija "zadržava" konačno množenje, sve dok ne stigne do izračinavanja faktorijela jedinice.
Prvo je 5!=5*4! (zadržava, tj. zove ponovo f-ju - ta petica "visi", dok ne stignu ostali rezultati poziva), pa ima 4!=4*3! itd, dok ne stigne do 2=2*1! (a 1! ume da izračuna neposredno). Onda se izmnoži sve "unazad" i funkcija se završi.
(Nije baš 100% korektno objašnjenje, ali je poenta tu, bar se nadam. )


_{[Ovu poruku je menjao maksvel dana 04.04.2010. u 15:32 GMT+1]}

Jedan mali dodatak maksvel-ovom objasnjenju.

Rekurzivna funkcija poziva samu sebe, uvek sa nekom drugom vrednoscu argumenta i podesena je da u jednom trenutku izadje i pozivaocu vrati resenje.

Druga vrednost argumenta se postize sa n-1 a izlazi se kada se ispuni (n<=1).

Recursion:
If you don't get it, see Recursion.

sve je to ok, ali jos uvijek ne kontam zasto nece ispisat uvijek rezultat 1, jer nebitno koji broj proslijedim kao argument funkciji, on će doći na kraju do n<=1, tj do n=1 i onda bi nfakt postao 1.

Pazi... Gledaj na sledeci poziv kao na izvrsenje nove funkcije, znaci kad se prvi put pozove sa parametrom npr. 5, ta petica ceka da se vrate sve ostale vrednosti i da se izmnozi sa njima... nfakt ti postaje 1 u poslednjem pozivanju i ta vrednost se vraca funkciji koja je pozvana pre toga... Nadam se da ti je malo jasnije, ja sam to na taj nacin skapirao, mozda ce neko umeti malo bolje da ti objasni :)

Lokalne promenljive unutar funkcije (kao i parametri funkcije) su jedinstveni za taj poziv funkcije. Ako funkcija poziva samu sebe pet puta onda se negde u memoriji (na takozvanom steku) nalazi pet promenljivih nfakt, svaka unutar sopstvene funkcije. Tih pet promenljiva ne dele istu vrednost, nego svaka ima svoju.

Ajde da se i ja oprobam u objasnjavanju. :)
Ovako recimo da pozivas f-ju sa parametrom 4 (uzeo sam ovu vrednost da objasnjavanje ne bi potrajalo).
Znaci negde u kodu imas promenljivu kojoj dodeljujes rezultat f-je fakt


ovo se desava u memoriji, manje vise:



e sad, posto je 4 vece od 1 prolazi se u else deo, a tu opet imamo poziv ove iste f-je samo sa parametrom 3



sad opet uslov nije zadovoljen i opet se prelazi u else deo, i opet tu imas poziv f-je, ali sada sa parametrom 2



opet ista prica i opet poziv f-je samo sa parametrom 1



e sad, ova je jako bitna, ovde else deo nece biti odradjen, jer je 1 <= od 1, i nfakt ce dobiti vrednost 1 i vratiti 1 kao rezultat.
ALI NE U U GLAVNI PROGRAM, NEGO U F-JU KOJA JE TU F-JU POZVALA. U ovom slucaju f-ju fakt sa parametrom 2.
Pa ce f-ja sa parametrom 2 izgledati ovako ustvari:

ova f-ja ce vratiti rezultat 2*1 sto je 2 i proslediti taj rez f-ji koja je nju pozvala, tj f-ji sa parametrom 3, koja ce posle vracanej vrednosti da izgleda ovako


to znaci da ce f-ja fakt(3) vratiti 2*3 sto je 6 f-ji koja je nju pozvala, tj f-ji fakt(4)


a ova f-ja vraca 4*6 sto je 24 tamo gde je ona pozvana, tju glavni program, a to je i vrednost faktorijela broja 4.
Jos jedna bitna osobina: F-JA SE NECE ZAVRSITI DOK SE NJOJ NE VRATI VREDNOST F-JE KOJU JE ONA POZVALA, znaci fakt(4) ce cekati dok fakt(3) ne vrati njemu vrednost, a fakt(3) ce cekati dok fakt(2) ne vreti vrednost, i tako redom... Tek kad se f-ja koja nema poziva zavrsi onda se krece unazad.

grabber, rekurzija je vrlo jednostavna i moćna tehika, ali ujedno i veliki potrošač resursa... Glavno je da treba zapamtiti da kada funkcija/procedura poziva samu sebe, pre poziva snimi na steku sve promenljive koje se u njoj koriste i tačku sa koje poziva samu sebe, pa kad jednom stigne do uslova kojim regularno izadje (return), vraća se na predhodno zapamćenu tačku prekida i tako nastavlja dalje dok stek ne bude prazan (uslovno rečeno)...

Najjednostavniji primer je rekurzivno izračunavanje faktorijela koje je i ovde navedeno. Dakle, faktorijel od n (n!) je definisan samo za pozitivne cele brojeve sa izuzetkom 0, gde je 0! =1, za negativne vrednosti treba vratiti grešku. To je osnovna postavka zadatka.

Uzmimo na primer 5!, to je x=n*(n-1)!, gde n ide od 5 do 1.

Za fakt(5), odnosno n=5 proveri da li je n=0, ako nije, snimi sve promenljive, zapamti gde si stao i pozovi sam sebe sa nfakt = 5* fakt(4), nfakt je nedefinisano.

fakt(4), isto kao i predhodno samo 4* fakt(3) itd.

Kada dodje do poziva sa nfakt = 1 * fakt(0), pri put će nam za n biti poznata vrednost nfakt, a to je 1.

Sada funkcija vraća vrednost 1 i sa steka skida vrednost promenjive n (koja je 1), nfakt (nedefinisan) i pozicije odakle je pozvala samu sebe. Kako je nfakt=n*fakt(n-1), odnosno nfakt=1*fakt(1-1), a vrednost fakt(0) smo upravo dobili (1), možemo da izračunamo nfakt=1*1=1.

Dalje n=2, vraća se 1, a to je vrednost za fakt(1), pa je sada nfakt:= 2 * fakt(1)= 2 * 1 = 2
Dalje n=3, vraća se 2, a to je vrednost za fakt(2), pa je sada nfakt:= 3 * fakt(2)= 3 * 2 = 6
Dalje n=4, vraća se 6, a to je vrednost za fakt(3), pa je sada nfakt:= 4 * fakt(3)= 4 * 6 = 24
Dalje n=5, vraća se 24, a to je vrednost za fakt(4), pa je sada nfakt:= 5 * fakt(4)= 5 * 24 = 120

Tu se proces obustavlja, jer je stek prazan i vraća se 120.

Faktorijel je možda jednostavan primer, ali nije baš zgodan pošto se može jednostavno rešiti jednom for petljom, tako da to može da zbunjuje zašto se uopšte koristi rekurzuja. Mnogo bolji primer je QSort ili rešenje Hanojskih kula. Oba algoritma su malo složenija i pokazuju šta se tačno dešava sa promenljivama i tačkama prekida. Još drugi jedan dobar primer kojeg se mogu setiti za primenu rekurzije je brisanje binarnog stabla.

_{[Ovu poruku je menjao sasaz2008 dana 05.04.2010. u 22:11 GMT+1]}

Pogledajmo šta se dešava kada funkcija ima argument 1: u trećem redu tijela funkcije nfakt uzima vrijednost 1, zatim se izvrsava šesti red, tj. funkcija vraća vrijednost 1 a ne vrijednost koju je imala kada je prethodni put izvršena pomnozenu sa 1.
Inače, rekurzivna funkcija je funkcija koja poziva samu sebe.

Ispravka:

#include <iostream>
using namespace std;

long fakt(int n)
{
long nfakt;
if (n==1)
return 1;
else return n*fakt(n-1);
}

main()
{
int m;
cout<<"Unesi cijeli broj: ";
cin>>m;
if (m>=1)
cout<<m<<"!="<<fakt(m);
else cout<<"Faktorijel negativnog broja nije definisan!";
return 0;
}

Hvala puno ljudi, mislim da sam napokon shvatio! I sad, zasto i gdje koristiti rekurziju, kada je gotovo nemoguce odraditi posao sa malo vecim brojevima u nekom realnom vremenskom periodu?

Rekurziju gledaj da koristis samo za resavanje rekurzivnih problema, tj problema koji nemaju iterativno resenje, svaki problem koji mozes i iteretivno i rekurzivno uvek radi iterativno.
Neki od tih problema su pretraga binarnog stabla, brisanje binarnog stabla (skoro sve u vezi sa stablima) i ima jos nekih.
Faktorijel je interesantno problem koji se resava iterativno, a u svakoj knjizi u kojoj ima objasnjenje rekurzije se nalazi bas resavanje faktorijela. :)
Sto se naravno ne radi rekurzijom.
Znaci samo ako ne mozes nesto da resis iterativno onda rekurzijom (to je tako u 99% slucajeva), ima i problema koje je bilje resiti rekurzivno, npr sortiranje niza (quicksort), ali ih je mnogo manje.

grabber,

Kao prvo, svaki rekurzivni algoritam se može prevesti u nerekurzivni (sam simuliraš stek), ali je onda kod malo nečitljiviji.

Drugo, stek je u mnogim programskim jezicima ograničen na veoma male vrednosti, koje se mere KB. To se može i promeniti, ali za to treba dobro poznavati kompajler.

Treće, rekurzija se najčešće koristi tamo gde je potrebna provera raznih kombinacija, kao recimo u šahu, traženje izlaza iz lavirinta, pronalaženje najkraćeg puta od mesta A do mesta Z i sl. Koliko će vremena biti potrebno, zavisi od broja kombinacija koje se ispituju i složenosti algoritma koji svaku kombinaciju obradjuje. Obično brzina za izvršavanje nekih realnih problema (kao što je nalaženje najkraćeg puta) danas nije nikakvo ograničenje, ali jeste ograničenje koje nameće stek. U teoriji postoji način da se izračuna vreme potrebno za izvršavanje, ali to moraš da izračunaš za konkretan algoritam. Generalan način kako se to radi možeš da nadješ u svakoj knjizi za učenje osnova algoritama ili potraži na internetu.

Wajda,procitah tvoj komentar,a upravo se prilicno mucim sa quick sortom...pa da li bi bio problem da mi pojasnis nekako?
Takodje, radim rekurziju u stablima,i veoma se mucim,ali vasi komentari pomazu!

****jedan problem u stablima****
Potrebno je da nadjem visinu prvog cvora u stablu koji nema jedno dete barem

public int visinaCvoraBezDeteta(CvorStabla koren){
if(k==null) return 0;
if(k.levo==null || k.desno==null) return 1;
return 1+Math.min(visinaCvoraBezDeteta(k.levo),visinaCvoraBezDeteta(k.desno));
}

// e sad mene buni ovaj kec u posledjem returnu
//moje je misljenje da treba bez njega,jer ovako dobijamo visinu za 1 vecu od stvarne

Jesam li u pravu?

Funkcija ne vraća visinu nego nivo čvora. Koren stabla je na prvom nivou i ako je koren rezultat onda funkcija vraća 1. Ako bi pozvao funkciju sa null onda bi vratila 0. Meni se to čini kao dobra organizacija, ali ako ti ne odgovara onda napravi novu funkciju koja hendluje parametar null kako već misliš da treba, a inače vraća vrednost visinaCvoraBezDeteta(x) - 1 kao rezultat.