REKURZIVNI ALGORITMI
Rekurzija je metod u programiranju za rešavanje složenih problema iterativnim ponavljanjem određenog postupka(funkcije)koja rešava deo manjeg problema u tom složenom, koji se rešavaju ponavljanjem istog postupka(funkcije) više puta(rekurzivno).
Dati problem koji je složen se prvo podeli na više manjih problema, koje je lakše rešiti.Svaki taj potproblem se rešava nezavisno jedan od drugog i kada se svaki od nih reši, onda se ta rešenja kombinuju in a taj način rešava složen problem, od koga se pošlo.
Za razliku od petlji gde se određen postupak koji se ponavlja navodi u telu petlje, rekurzivni postupak je takođe iterativan, ali postupak koji se ponavlja je sam algoritam koji sam sebe poziva više puta direktno ili indirektno pozivanjem neke naredbe ili funkcije, koja onda poziva dati algoritam(funkciju).
Dati problem koji je složen se prvo podeli na više manjih problema, koje je lakše rešiti.Svaki taj potproblem se rešava nezavisno jedan od drugog i kada se svaki od nih reši, onda se ta rešenja kombinuju in a taj način rešava složen problem, od koga se pošlo.
Za razliku od petlji gde se određen postupak koji se ponavlja navodi u telu petlje, rekurzivni postupak je takođe iterativan, ali postupak koji se ponavlja je sam algoritam koji sam sebe poziva više puta direktno ili indirektno pozivanjem neke naredbe ili funkcije, koja onda poziva dati algoritam(funkciju).
Rekurzija primer: Izračunavanje stepena Xn
Xn=X*X*X* … *X= X*Xn-1 * X
Rešenje pomoću petlje
int XN=1;
for(int i=0; i
{
printf("XN=%d\n",XN);
for(int i=0; i
XN=XN*X;
}printf("XN=%d\n",XN);
Rešenje pomoću rekurzije
Treba da se napravi funkciju koja računa n-ti stepen broja x kao proizvod broja x i stepena broja x za jedan stepen manje tj.
Xn = Xn-1 * X
Ta funkcija kao parametar treba da primi osnovu stepena X, kao i izložilac stepena n. Za računanje n-1 stepena broja X može se pozvati ista funkcija, kojoj se sada prosleđuju kao parametri osnova X i kao drugi parametar izložilac, ali ovoga puta n-1. Postupak se opet dalje rekurzivno poziva sve dok se izložilac smanji do vrednosti 1. Unutar funkcije treba postaviti ispitivanje uslova (n==1) preko naredbe if i ako je ispunjen u tom slučaju funkcija treba da vrati vrednost 1 jer je:
X0 = 1
Algoritam izvršavanja se može videti na slici ispod:
Slika 1: Rekurzivni algoritmi. Izračunavanje x na n-ti stepen
Funkcija stepen( ) se prvi put poziva u funkciji main i tad je vrednost izložioca n. Unutar funkcije se proverava da li je stepen stigao do 1, što će se desiti u poslednjoj iteraciji, koja će se zapravo prva završiti. Funkcija tada vraće kao povratnu vrednost 1 i taj rezultat se koristi u pretposlednjem pozivu da bi se odredila vrednost koja se računa unutar funkcije. Zatim pretposlednja vraća vrednost i tako redom sve dok se ne stigne do početnog poziva unutar main metode. Tek tada imamo vrednost koja se tražila izračunatu i ona se može prikazati.
Kod koji ovo rešava:
Kod koji ovo rešava:
#include < iostream >
int stepen(int x, int n)
{
int main() {
using namespace std;
int stepen(int x, int n)
{
if(n==1)
}
return 1;
elsereturn x*stepen(x,n-1) ;
int main() {
int XN,X,N;
cin >> X;
cin >> N;
XN=stepen(X,N);
cout << XN << endl;
return 0;
}cin >> X;
cin >> N;
XN=stepen(X,N);
cout << XN << endl;
return 0;
Fibonačijev niz
|
Zadatak kojim se određuje n-ti član Fibonačijevog niza, može se između ostalog rešiti rekurzijom: Pogledajte više o tome na strani:
Fibonačijev niz |
|
|
Sledeće
Rekurzija-primeri >| |