Nedostaci rekurzije:
uvećano vreme izvođenja
neki jezici ne podržavaju rekurziju
Formalna pravila za uklanjanje rekurzije:
1. Na početku funkcije umetne se deklaracija steka, inicijalno praznog. Stek služi za pamcenje svih podataka vezanih uz rekurzivni poziv: argumenata, vrednosti funkcije, povratne adrese
2. Prva izvršna naredba dobije oznaku L1.
Svaki rekurzivni poziv zamenjen je naredbama koje obavljaju sledeće:
3. Smesti na stek vrednosti svih argumenata i lokalnih promenljivih.
4. Kreiraj i-tu novu oznaku naredbe Li i smesti i na stek. Vrednost i će se koristiti za izračunavanje povratne adrese. U pravilu 7. je opisano gde se u programu smešta ta oznaka.
5. Izračunaj vrednosti argumenata ovog poziva i pridruži ih odgovarajućim formalnim argumentima.
6. Umetni bezuslovni skok na početak funkcije.
7. Oznaku kreiranu u tački 4. pridruži naredbi koja uzima vrednost funkcije s vrha steka. Dodaj programski kod koji tu vrednost koristi na način opisan rekurzijom.
Ovime su uklonjeni svi rekurzivni pozivi. Umesto svake naredbe return dolazi:
8. Ako je stek prazan, obavi normalnu naredbu return.
9. Inače, uzmi vrednosti svih izlaznih argumenata i stavi ih na vrh steka.
10. Odstrani sa steka povratnu adresu ako je bila stavljena, i pamti je u nekoj promenljivoj.
11. Uzmi sa steka vrednosti za sve lokalne promenljive i argumente.
12. Umetni naredbe za izračunavanje izraza koji sledi neposredno iza naredbe return i smesti rezultat na stek.
13. Idi na naredbu s oznakom povratne adrese.
1. Implementirajte rekurzivnu verziju funkcije binarne pretrage, a potom uklonite rekurziju prema predavanom algoritmu za eliminaciju rekurzije.
U ovom promeru radi se o tzv. repnoj rekurziji (kada je poslednji iskaz funkcije rekurzivni poziv te iste funkcije). Tada,
ako je poslednji iskaz funkcije P, pre povratka, poziv funkcije Q, taj poziv se moze zameniti GOTO iskazom na pocetak funkcije Q.
Ako je P=Q, onda se GOTO iskaz usmerava na pocetak funkcije P.
Algoritam binarnog pretrazivanja - rekurzivna funkcija nad nizom a sa n clanova:
int binarpretr(int k, int l, int d) /* k =kljuc koji se trazi, l= indeks levog kraja niza, d=indeks desnog kraja niza */
{
int x, bp; /* sredina niza, rezultat binarne pretrage */
if (d< l) return n+1; /* IZLAZ iz rekurzije – neuspeh */
else
{
x=(l+d) / 2;
if (k == a[x]) return x;
else
if (k < a[x])
{
bp=binarpretr(k,l,x-1);
return bp;
}
else
{
bp=binarpretr(k,x+1,d);
return bp;
}
}
}
Ova funkcija ima samo jedan rekurzivni poziv (izvrsava se ili iskaz bp = binarpretr(k,l,x-1) ili iskaz bp = binarpretr(k,x+1,d). Definicija ove funkcije se prvo moze preformulisati tako da i u zapisu funkcije figurise samo jedan rekurzivni poziv:
int binarpretr(int k, int l, int d)
{ int x, bp;
if (d< l) return n+1;
else
{ x=(l+d) / 2;
if (k == a[x]) return x;
else
{
if (k < a[x]) d = x-1;
else l=x+1;
bp=binarpretr(k,l,d);
return bp;
}
}
}
Sada se funkcija moze transformisati tako da se eliminise repna rekurzija:
int binarpretr(int k, int l, int d)
{
int x;
label: if (d< l) return n+1; /* IZLAZ IZ REKURZIJE */
else
{
x=(l+d) / 2;
if (k == a[x]) return x;
else
{
if (k < a[x]) d = x-1;
else l=x+1;
goto label; /* ZAMENA ZA REKURZIVNI POZIV */
}
}
}
Da bi se eliminisao GOTO iskaz iz prethodne deklaracije funkcije, potrebno je grupisati iskaze koji su u petlji, i iskaze kojima funkcija dobija vrednost
i zavrsava izvrsavanje (return . . . ):
int binarpretr(int k, int l, int d)
{
int x;
label: if (d>= l)
{ x=(l+d) / 2;
if (k ! = a[x])
{
if (k < a[x]) d = x-1;
else l=x+1;
goto label;
}
else return x;
}
else return n+1;
}
Sada se poccetni deo deklaracije funkcije binarpretr, koji se ponavlja pomocu GOTO iskaza, moze zameniti eksplicitnim iskazom petlje:
int binarpretr(int k, int l, int d)
{
int x;
if (d>= l)
{
x=(l+d) / 2;
while(d >= l && k ! = a[x])
{
if (k < a[x]) d = x-1;
else l=x+1;
x=(l+d) / 2;
}
}
if (a[x]==k) return x;
else return n+1;
}
Najzad, ako se while iskaz zameni do-while iskazom (s obzirom na prvo bezuslovno izvrsenje iskaza x=(l+d) / 2 to ima smisla), dobija se deklaracija iterativne funkcije za binarno pretrazivanje, gotovo identicna iterativnoj funkciji binarne pretrage (K&R verzija).
int binarpretr(int k, int l, int d)
{
int x;
if (d>= l)
do
{
x=(l+d) / 2;
if (k < a[x]) d = x-1;
else l=x+1;
}while (d >= l && a[x]!=k);
if (a[x]==k) return x;
else return n+1;
}
Zadaci za vezbu:
Implementirajte rekurzivnu funkciju (program) za traženje indeksa najvećeg člana u nizu, a potom uklonite rekurziju prema navedenim pravilima.
Implementirajte rekurzivnu funkciju (program) za trazenje najveceg zahednickog delioca dva prirodna broja, a potom uklonite rekurziju.
Implementirajte rekurzivnu funkciju (program) za PREORDER obilazak binarnog stabla, a potom uklonite rekurziju.
Implementirajte rekurzivnu funkciju (program) za INORDER obilazak binarnog stabla, a potom uklonite rekurziju.
Implementirajte rekurzivnu funkciju (program) za POSTORDER obilazak binarnog stabla, a potom uklonite rekurziju.
Implementirajte
rekurzivnu funkciju (program) za resavanje problema hanojskih kula,
a potom uklonite rekurziju.