18/19: Programiranje IT 2

Rekurzivne funkcije su funkcije koje pozivaju same sebe.

Primer pomoću kojeg ćemo ilistrovati kako funkcioniše rekurzija će biti izračunavanje faktorijela nekog broja. Da se podsetimo iz matematike: n!=1*2*3*...*n

To se može napisati i na sledeći način:

Drugim rečima, da bi se izračunao n!, potrebno je izračunati (n-1)! i rezultat pomnožiti sa n. Za izračunavanje (n-1)! potrebno je izračunati (n-2)! i tako redom, sve dok se ne dođe do n=0, za koje je rezultat 1. Sada je potrebno taj rezultat pomnožiti sa 1, da bi se dobila vrednost za 1!, taj rezultat se množi sa 2 da bi se dobila vrednost za 2! i tako redom, sve dok se ne stigne dotle da množeći (n-1)! sa n ne dobije konačan rezultat za n!.

Opšta karakteristika svih rekurzivnih problema je da se rešavanje svodi na rešavanje istog problema sa izmenjenim parametrima. Prilikom programiranja to znači da rekurzivna funkcija poziva samu sebe sa izmenjenim argumentima. Da bi ovaj postupak mogao da se ikada završi, mora da postoje neke specijalne vrednosti parametara (argumenata) za koje rezultat nije definisan rekurzivno - to su obično neke konstante.

Primer: kako bismo rešili funkciju za izračunavanje faktorijela:

int faktorijel(int n)
{
   if(n>0)
      { return n*faktorijel(n-1); }
   else
      { return 0; }
}

Vrednost funkcije se dobija tako da se ili izračunava ona formula, ili se dobija konstanta 1. Izračunavanje formule dovodi do toga da se poziva ista funkcija ali sa argumentom (n-1). Izračunavanje vrednosti faktorijel(n-1) zahtevaće izračunavanje faktorijel(n-2) i tako redom, sve dok parametar ne postane nula. Tada se izborom konstante 1 za vrednost funkcije dobija prvi međurezultat za poziv faktorijel(0). Na osnovu tog rezultata dobija se vrednost za faktorijel(2) i tako redom, sve dok se ne dobije vrednost funkcije za prvobitni poziv faktorijel.