Citat:
Goran Arandjelovic: Za rekurziju UVEK treba definisati bazni slučaj, a ne oslanjati se na tail recursion optimizaciju.
Kakve veze ima rekurzija sa optimizacijom? Rekurzija je svođenje složenih slučajeva na proste u nekom broju koraka, pri čemu se rešavaju neposredno. Štaviše, rekurzija po pravilu daje manje efikasna rešenja od iterativnih.
Primer: Izračunavanje elemenata Fibonačijevog niza:
Code (cpp):int fib_recursive(int k)
{
if (k == 1 || k == 2) {
return 1;
} else if (k > 2) {
return fib_recursive(k - 1) + fib_recursive(k - 2);
} else {
throw("error");
}
}
int fib_iterative(int k)
{
if (k < 1) {
throw("error");
}
int a0 = 0, a1 = 1;
for (int i = 1; i < k; ++i) {
int t = a0 + a1;
a0 = a1;
a1 = t;
}
return a1;
}
Rekurzivna funkcija se računa u eksponencijalnom vemenu i linearnom prostoru (računajući nagomilavanje steka), a iterativno u linearnom vremenu i konstantnom prostoru. Za iterativno rešenje je lako proceniti složenost. Rekurzija uvek izbacuje rezultat 1 kada se slučaj ne svodi na prostiji, tako da će se sve svesti na sabiranje jedinica. Primera radi
fib(5)=fib(4)+fib(3)
=(fib(3)+fib(2))+(fib(2)+fib(1))
=((fib(2)+fib(1))+1)+(1+1)
=((1+1)+1)+(1+1)
Ko ne veruje, može da ubaci brojače i dobiće da je broj sabiranja koji se obavi za izračunavanje fib(k) tačno fib(k)-1, a broj neposrednih izračunavanja tačno fib(k). No, poznato je da Fibonačijev niz eksponencijalno brzo raste, tako da je vreme izvršavanja eksponencijalno. Korišćeni prostor je linearan, jer za k>2 nema rekurzivnih spustova koji su duži od k-2 (argument se uvek smanjuje za 1), a postoji rekurzivni spust dužine k-2 (u izračunavanju fib(k) se koristi izračunavanje od fib(k-1) u čijem se izračunavanju koristi fib(k-2) itd.).
Kada rekurziju treba koristiti? Skoro nikad. Ako ne postoji potreba za gomilanjem steka, to treba rešiti petljom. Sledeći primer pronalazi prvi član neopadajućeg niza koji nije manji od date vrednosti:
Code (cpp):int binary_search(double value, double array[], int size)
{
int left = 0, right = size;
while (left < right) {
int mid = (left + right) >> 1;
if (array[mid] < value) {
left = ++mid;
} else {
right = mid;
}
}
return left;
}
Kada se stek gomila, a nemamo kontrolu koliko može da se gomila, ni slučajno ne koristiti rekurziju, već ako je algoritam baš prirodno rekurzivan, onda simulirati rekurziju korišćenjem dinamičkog steka (flood fill, rešavanje lavirinta itd). Nju treba koristiti samo u slučaju da se stek gomila do neke kontrolisane granice, a takvi slučajevi su retki (razna balansirana stabla, minimaks algoritam za igranje igara kao što je šah itd).
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Re: Ponavljanje main funkcije
