U matematici, rekurzija je takav algoritam, odnosno notacija ili pravilo opisa objekta, u čijim se definicijama kao parametar ili argument pojavljuju (i) sami objekti.

Rekurzija u matematici omogućuje kompaktno definisanje proizvoljno velikog skupa vrednosti objekata minimalnim skupom izjava. Recimo: sa samo dve izjave definišemo skup prirodnih brojeva.

1 je prirodan broj.
ako je n (n>1) prirodan broj, onda je i n+1 prirodan broj.

U programiranju označava situaciju kada procedura ili funkcija poziva sama sebe. tj. kada se u definiciji funkcije, rekurzivno, kao parametar, javlja ista funkcija, jednom ili više puta, ali s drugoim vrednostima argumenta, Međutim to nije jedini slučaj. Postoji i uzajamno pozivanje dve (ili više) funkcije kada funkcija f() poziva funkciju g() a ova opet poziva funkciju f(), i tako ponovo.

U programskim jezicima, rekurzivni algoritmi implementirani su kao podprogrami (procedure ili funkcijski podprogrami) radi mogućnosti rekurzivnog pozivanja. PASCAL je jedan od nekoliko programskih jezika visokog nivoa u kojima je dopušteno opisivanje i izračunavanje rekurzivnim algoritmima.

Razumevanje rekurzije

Da bi ste shvatili rekurziju, prvo morate shvatiti rekurziju!

Humor se ovde krije u igri reči, i to iz dva razloga. Prvo rekurzivne funkcije su one koje pozivaju same sebe, pa otud shvatanje rekurzije zavisi id shvatanja rekurzije. Drugo činjenica je da je rekurziju teško razumeti, i izgleda da je neki ljudi shvataju a neki ne.

Ovo poslednje ne treba prihvatiti kao stanje koje se ne može popraviti. Shvatanje rekurzije nije nemoguće ako sledite nekoliko sledećih jednostavnih uputstava. Osnova shvatanje rekurzije je prvo u tome, da shvatite kako rešiti problem za jedan nivo jednostavniji, i drugo, da naučite kao da pratite rekurzivnu funkciju.

Praćenje je neverovatno korisno kada ste početnik u savladavanju rekurzivnih poslova. Učenici veruju da funkcija poziva sama sebe, što dovodi do nepredvidivih tokova misli i skretanja spravog puta. Oni u glavnom ne shvataju da kad funkcija poziva sama sebe, ona se u stvari ponaša potpuno isto kao kad poziva drugu funkciju.

Ako niste u stanju da pravilno pratite rekurziju, teško da možete verovati da ona radi ispravno.

Šta je ironija: kada ispratite rekurzivnu funkciju nekoliko puta (recimo 10 do 20 puta na različitim slučajevima), tada počinjete verovati poslu koji obavlja rekurzija, i odjednom više ne pratite rekurzivni kod, sem u slučaju kad ga morate dibagirati.

Većina ljudi prolazi tri faze u procesu učenja rekurzije. Prvo, oni je mrze, jer ne mogu da je razumeju. Zatim, je vole jer su razumeli ovaj misteriozni proces. I na kraju ponovo je mrze jer misle da je neefikasna. Naročito zato što rekurzivna rešenja zahtevaju bar O(n) memorije, dok iterativna daju rešenja u O(1) prostora. Ipak za mnoge probleme kod kojih memorijski prostor nije velika briga, rekurzija daje jednostavna rešenja, lakа za praćenje.

Rekurzivni problemi

Mnogi problemi se mogu i rešiti rekurzivno, npr. igre svih tipova od jednostavnih kao što su problem Hanojskih kula do složenih, kao sto je šah. U igrama, rekurzivna rešenja su naročito pogodna kada zaključite da konačno rešenje zavisi od rešenja koje je za jedan (ili nekoliko) korak manje.

Rekurzivni, kao i svaki drugi algoritam, mora biti okarakterisan sledečim osobinama:

da je opisan u konačnom broju koraka, i
da se izračunavanje vriednosti završi nakon konačnog broja izračunavanja.

Dok je prvu osobinu relativno jednostavno ostvariti, za ostvarenje druge osobine potrebno je uvesti tvz. uslov završetka. Ako se rekurzivni algoritam posmatra kao funkcija jednog ili više argumenata, kažemo da će se izračunavanje vrednosti po tom algoritmu završiti ako se pri svakom pozivu rekurzivne funkcije bar jedna od izračunatih vrednosti približava uslovu završetka.

Mnoge matematičke funkcije se mogu definisati rekurzivno:

Faktorijel
Fibonačijevi brojevi
Određivanje NZD po euklidovom algoritmu (najveći zajednički delilac)

Uslov završetka je ekstremno važan kada radimo sa rekurzivnim funkcijama. Ako se izostavi, ili pogrešno odredi, tada će funkcija nastaviti da poziva samu sebe sve dok program ne popuni ceo stek poziva tj. ne potroši svu slobodnu memoriju! Naravno u tom slučaju rezultati su neupotrebljivi.

Nedostatak ispravnog uslova prekida u rekurzivnoj funkciji je uvek katastrofalan!

Pri upotrebi globalnih promenljivih unutar geklaracije koda rekurzivnih funkcija, takođe treba biti oprezan.

Strukture podataka se takođe mogu rekurzivno definisati. Jedna od najvažnijih klasa struktura - stabla - dozvoljavaju rekurzivne definicije koje vode do jednostavnih (i efikasnih) rekurzivnih funkcija za njihovu obradu. Isto važi i za grafove. Sa rekurzijom ćemo se sresti i kod sortiranja nizova pomoću quick-sort algoritma.

Primer 1 - Faktorijel

Napisati program koji izračunava n! ako se unosi prirodan broj n sa tastature.

{ dve su stvari presudne:

 1. 0! = 1.         - imamo kriterijum završetka.

 2. n! = n * (n-1)! - zavisnost problem od jednostavn. za korak.}

Var n:integer;

Function Faktorijel(x:integer):longint;

Begin

  if x = 0

    then Faktorijel := 1

    else Faktorijel := x * Faktorijel(x-1);

End;

Begin

  Write('Unesite prirodan broj n  = '); Readln(n);

  Writeln('N faktorijel iznosi : ', Faktorijel(n));

End.

Primer 2 - Fibonačijevi brojevi

Napisati program koji izračunava niz fibonačijevih brojeva ako se unosi prirodan broj n sa tastature.

{ za razliku od preth. primera, ovde imamo tri krične stvari:

 1. fib(0) = 1                   - imamo jedan krit. završetka,

 2. fib(1) = 1                   - imamo drugi krit. završetka,

 3. fib(n) = fib(n-1) + fib(n-2) - problem zavisi od dva jednost.:

                                   prethodnog i pretprethodnog.}

Var n:integer;

Function Fibonaci(x:integer):longint;

Begin

  if (x = 0) or (x = 1)

    then Fibonaci := 1

    else Fibonaci := Fibonaci(x-1) + Fibonaci(x-2);

End;

Begin

  Write('Unesite prirodan broj <= 45, n  = '); Readln(n);

  Writeln('Fibonacijev broj za broj n je : ', Fibonaci(n));

  { ako želite niz fibonačijevih brojeva

    upotrebite ispis u brojačkom ciklusu. }

End.

Primer 3 - Određivanje NZD

Napisati program koji izračunava najveći zajednički delilac, ako se dva prirodna broja a i b unose sa tastature.

Var a, b : longint;

Function NZD(x, y :longint):longint;

Begin

  if y = 0

    then NZD := x

    else NZD := NZD(y, x mod y);

End;

Begin

  write('unesi prvi  broj,  a: '); Readln(a);

  write('unesi drugi broj,  b: '); Readln(b);

  writeln('NZD(',a,',',b,') je ', NZD(a, b));

End.

Algoritmi

Grafovi