Razlaganje programa na manje dijelove - funkcije

Rekurzivne funkcije

Rekurzivna funkcija je funkcija koja poziva samu sebe. U pravilu, rekurzivna rješenja su kraća, ali je za njihovo izvođenje potrebno više vremena i memorije.

Svaka rekurzija mora imati uvjet zaustavljanja koji će omogućiti izlazak iz rekurzije. U protivnom rekurzivna funkcija će se izvoditi beskonačno. Također svaki poziv rekurzije mora se približavati uvjetu zaustavljanja.

Za pohranjivanje rezultata i povratak iz rekurzije upotrebljava se STOG (eng. stack). Stog je dinamički dio memorije koji se upotrebljava za pohranjivanje podataka koji se privremeno koriste u određenim dijelovima programa. Broj podataka na stogu je promjenljiv, ali količina memorije za stog je ograničena.

Stog se puni i prazni prema principu zadnji unutra – prvi van (eng. LIFO – last in – first out). Za bolje razumijevanje stoga često se koristi analogija s hrpom tanjura (npr. u restoranima): posljednji tanjur stavljen na hrpu se uzima prvi.

Na stogu se koriste dvije operacije: push i pop. Operacija push šalje podatak na stog dok operacija pop skida podatak sa stoga.

Primjer rekurzije je izračunavanje n! (n!=1*2*...*n)

Zadatak: Prisjetite se načina na koji smo do sada za zadani broj n računali n!.

Do sada smo koristili definiciju n!=1*2*3*...*n.
No, n! možemo definirati i drugačije: n!=n*(n-1)!.
Ovo je rekurzivni način definiranja n!