|
Rekurzivne funkcije
*definicija: REKURZIVNA FUNKCIJA- funkcija koja poziva samu sebe
*opći oblik:
tip_f-je ime_rek_f-je (int t)
{
...
if (uvjet)
ime_rek_fje(t-1);
...
if (uvjet1)
return x;
}
* rekurzivna funkcija uvijek sadrži barem dva uvjeta:
- ako je ispunjen prvi uvjet funkcija poziva samu sebe
-ako je ispunjen drugi uvjet, funkcija vraća vrijednost u funkciju iz koje je pozvana
PRIMJERI:
*Za uneseni prirodni broj n, ispiši vrijednost n! .
npr: n=5 ----> treba vratit: 1*2*3*4*5 tj. 120
#include
int rekurzija (int n)
{
if(n>1)
return n * rekurzija (n-1);
else
return 1;
}
main ()
{
int n;
scanf("%d",&n);
n=rekurzija(n);
return 0;
}
* Bakterije se razmnožavaju dijeljenjem na dvije, svaki sat. Napišite program koji će ispisati broj bakterija nastalih nakon 12 sati, od jedne!
0.sat: A 1
1.sat: B C 2
2.sat: B1 B2 C1 C2 4
3.sat:B11 B12 B21 B22 C11 C12 C21 C22 8
#include
int rekurzija (int n)
{
if(n>1)
return 2*rekurzija(n-1);
else
return 1;
}
main ()
{
int n;
n=12;
n=rekurzija(n);
printf("%d",n);
return 0;
}
* Latice ruže poslagane su u redove:
- 1.red: 1 latica
- 2.red: 1 latica
- svaki sljedeći red ima onoliko latica koliko imaju dva prijašnja zajedno.
Napiši program koji računa broj latica u n-tom retku.
Vidimo da vrijedi:
F0 = 0
F1 = 1
...
Fn= Fn-1 + Fn-2 za n e 2,
odnosno broj latica u n-tom retku jednak je Fibonnaccijevom broju
#include
int fib(int n)
{
if ((n == 0) || (n == 1))
return 1;
else
return fib(n-1) + fib(n-2);
}
int main(void)
{
int n;
scanf("%d", &n);
if (n<0)
printf("Ne moze biti negativan broj!");
else
printf("nBroj latica: %d", fib(n));
return 0;
}
* KULE HANOIA
Postoje tri štapa označena s A,B i C. Na prvom štapu su cilindrični diskovi promjenljive veličine. Zadatak je premjestiti sve diskove s štapa A na štap B u redoslijedu
kako se nalaze na štapu A.
Pri prebacivanju diskova treba poštovati sljedeće pravila:
§ Odjednom se smije pomicati samo jedan disk
§ Ne smije se stavljati veći disk iznad manjeg diska
§ Može se koristiti štap C za privremeni smještaj diskova, ali uz poštovanje prethodna dva pravila
- U čemu je ovaj problem rekurzivan? Pokušajmo definirati temeljni slučaj i pravilo rekurzije.
- Temeljni slučaj - je najjednostavniji slučaj kojeg svatko može riješiti. Ako kula sadrži samo jedan disk,tada je rješenje jednostavno: prebaci se taj disk na ciljni štap B.
- Rekurzivno pravilo - Ako kula sadrži N diskova, pomicanje diskova se može izvesti u tri koraka:
- pomaknuti gornjih N-1 diskova na pomoćni štap C
- preostali donji disk s štapa A pomaknuti na ciljni štap B
- zatim kulu od N-1 diska s pomoćnog štapa C treba prebaciti na ciljni štap B
- koristimo funkciju pomakni_kulu, a argumenti koji će nam biti potrebni su: broj diskova koje treba pomaknuti, ime početnog štapa , ime ciljnog štapa, ime pomoćnog štapa.
void pomakni_kulu(int n, char A, char B char C);
- funkcija koja će označiti prebacivanje jednog diska:
void pomakni_disk(char sa_kule, char na_kulu)
- Korištenjem ove funkcije i pravila rekurzije, funkcija pomakni_kulu se može napisati na sljedeći način:
void pomakni_kulu(int n, char A, char B, char C)
{
if (n == 1) {
pomakni_disk(A, B);
}
else {
pomakni_kulu (n - 1, A, C, B);
pomakni_disk (A, B);
pomakni_kulu (n - 1, C, B, A);
}
}
Ili još jednostavnije:
void pomakni_kulu(int n, char A, char B, char C)
{
if (n > 0)
{
pomakni_kulu (n - 1, A, C, B);
pomakni_disk (A, B);
pomakni_kulu (n - 1, C, B, A);
}
}
jer za slučaj kada je n=1 pomakni_kulu(0, ....) ne izvršava ništa pa se u tom slučaju izvršava funkcija pomakni_disk(A,B), što je pravilo temeljnog slučaja.
* Žaba želi prijeći rijeku skačući preko n listova lopoča. To radi u skokovima po dva ili tri lista prema naprijed ili prema natrag. Povratka na kopno nema (dakle, ne
može otići “ispred” prvog lista). Također, ne može skočiti niti iza zadnjeg lista (npr. ne može skočiti s lista n1 na list n+1 ). Skakutanje je gotovo kad žaba dođe na
n-ti list. Napišite (rekurzivnu) funkciju koja za zadani n (jedan od funkcijskih argumenata) vraća broj načina kojima žaba može izvesti opisano skakanje u najviše 17 koraka.
USPOREDBA REKURZIVNIH I ITERATIVNIH PROGRAMA I
- Za usporedbu rekurzivnih i iterativnih programskih rješenja progledajmo primjer za računanje sume prirodnih brojeva 1,2,..n
- Rekurzivni algoritam za sumu n brojeva je:
1) trivijalni slučaj: ako je n==1 suma(n) je jednaka 1
2) za ostale vrijednosti od n, suma(n) = suma(n-1)+n
USPOREDBA REKURZIVNIH I ITERATIVNIH PROGRAMA II
- U obje funkcije u svakom se koraku vrši jedno logičko ispitivanje, jedno zbrajanje i jedno oduzimanje. U rekurzivnoj funkciji se još gubi vrijeme i memorijski
prostor za privremeni smještaj argumenata funkcije
- Usporedbom ova dva primjera vidljivo je da iterativni programi daje brži proračun i manje zauzimaju memoriju. To je čest slučaj
- Ipak, preporučuje se korištenje rekurzivnih funkcija u onim slučajevima kada to prirodno odgovara prirodi problema
|
