Strukture podataka i algoritmi: Rekurzija

Strukture podataka i algoritmi

3.4 Rekurzija

Mogu se naci mnogi primeri rekurzije: tehnika je korisna i za definiciju matematickih funkcija i za definiciju struktura podataka. Naravno, ako se struktura podataka moze definisati rekurzivno, tada se moze i obraditi rekurzivnom funkcijom!

recur
Na latinskom, re- = nazad +
currere = izvrsavati
Desavati se iznova, narocito u ponovljenim intervalima.

3.4.1 Rekurzivne funkcije

Mnoge matematicke funkcije se mogu definisati rekurzivno:

faktorijel
Fibonacijevi brojevi
Euklidov NZD (najveci zajednicki delilac)
Furijeova transformacija

Mnogi problemi se mogu i resiti rekurzivno, npr. igre svih tipova od jednostavnih kao sto su problem Hanojskih kula do slozenih, kao sto je sah. U igrama, rekurzivna resenja su narocito pogodna kada, posto ste resili problem serijom rekurzivnih poziva, zelite da saznate kako ste dosli do resenja. Cuvajuci podatak o potezu izabranom u svakom trenutku, stek poziva upravo sadrzi put do resenja! Ovo ce biti detaljnije objasnjeno kasnije.

3.4.2 Primer: faktorijel

Jedan od najjednostavnijih primera rekurzivnih definicija je faktorijel funkcija:

faktorijel( n ) = if ( n = 0 ) then 1
                  else n * faktorijel( n-1 )

Prirodan nacin za racunanje faktorijela je pisanje rekurzivne funkcije koja odgovara ovoj definiciji:

function fact( int n )
	{
	if ( n == 0 ) return 1;
	else return n*fact(n-1);
	}

Primetimo da ova funkcija poziva samu sebe da izracuna sledeci clan. Na kraju ce doci do uslova prekida i izaci. Medjutim, pre nego sto dodje do uslova prekida, ona ce staviti n okvira poziva na stek poziva.

Uslov prekida je ocigledno ekstremno vazan kada radimo sa rekurzivnim funkcijama. Ako se izostavi, tada ce funkcija nastavi da poziva samu sebe sve dok program ne popuni ceo stek poziva - obicno sa umereno neprijatnim rezultatima!

Nedostatak ispravnog uslova prekida u rekurzivnoj funkciji je uvek katastrofalan!

Jos jedan cesto koriscen (i zloupotrebljavan!) primer rekurzivne funkcije je izracunavanje Fibonacijevih brojeva. Sledeci definiciju:

fib( n ) = if ( n = 0 ) then 1
                if ( n = 1 ) then 1
                else fib( n-1 ) + fib( n-2 )

mozemo napisati funkciju:

function fib( int n )
	{
	if ( (n == 0) || (n == 1) ) return 1;
	else return fib(n-1) + fib(n-2);
	}

Kratka i elegantna, ova funkcija koristi rekurziju da na lep nacin resi problem - ali je u stvari totalno neefikasna! Kasnije cemo se ponovo vratiti na ovaj problem i videti zasto je u ovom slucaju rekurzija ipak los izbor.

Strukture podataka se takodje mogu rekurzivno definisati. Jedna od najvaznijih klasa struktura - stabla - dozvoljavaju rekurzivne definicije koje vode do jednostavnih (i efikasnih) rekurzivnih funkcija za njihovu obradu.

Ali da bismo videli zasto su stabla tako vazne strukture, moramo najpre da se pozabavimo problemom pretrazivanja.

Kljucni pojmovi

Uslov prekida: Uslov koji prekida seriju rekurzivnih poziva - i sprecava program da iskoristi svu memoriju za okvire poziva!