Predavanje 11 - Rekurzivni algoritmi I

1. Uvod

Pojam rekurzije je fundamentalan u matematici i racunarstvu. U racunarstvu promatramo funkcije koje zovu same sebe kao sto u matematici imamo rekurzivne jednadzbe.

Svaka rekurzija mora imati zavrsni uvjet koji kaze kada se rekurzija prestaje izvrsavati. Nas osnovni motiv za studiranje rekurzija su strukture definane rekurzivno kao npr. stabla koja cemo diskutirati iduci puta.

1. Rekurzivni algoritmi i funkcijski pozivi

Rekurzivni algoritam rjesava problem tako da najprije rijesi jedan ili vise potproblema istog tipa. U C-u se koriste funkcije koje pozivaju same sebe tvz. rekurzivne funkcije.

Primjer: Euklidov algoritam za trazenje najvece zajednicke mjere (NZM) cijelih brojeva osniva se na jednostavnom principu:


Ovaj jednostavni algoritam u C-u se moze izraziti prirodno rekurzijom:
int euklid(int m, int n){ if(n==0) return m; return euklid(n, m%n); } Pozivajuci ovu funkciju sa euklid(314159, 271828) imamo i ove rekurzivne (ugnjezdene) pozive redom: euklid(271828, 42331) euklid(42331, 17842) euklid(17842, 6647) euklid(6647, 4548) euklid(4548, 2099) euklid(2099, 350) euklid(350, 349) euklid(349, 1) euklid(1, 0) najveca zajednicka mjera: 1

Svako rekurzivno rjesenje ima i svoju nerekurzivnu varijantu. Npr. kod euklidovog algoritma mogli smo postupati ovako.

int euklid(int m, int n){ int pom; while(n!=0){ pom=n; n=m%n; m=pom; } return m; }

Iako je ovo rijesenje sasvim korektno, rekurzivno rjesenje bolje opisuje samu rekurzivnu prirodu algoritma. Mi koristimo rekurziju da bi smo napisali slozene algoritme u kompaktnoj formi.

Interno program prevodioc kreira stog funkcijskih poziva sa kojima radi u rekurzivnom algoritmu. Iako moderni sistemi obicno imaju efikasno implementiran mehanizam rekurzivnih poziva, cesto je moguce napisati jednostavne rekurzivne programe koji su izuzetno neefikasni. Primjer racunanja prvih N clanova Fibonacijevog niza zadanog rekurzivno:


F(0)=1 F(1)=1 F(N+2)=F(N+1)+F(N), N >=0 Iz eksplicitne formule za rjesenje ove linearne rekurzije znamo da Fibonacijevi brojevi rastu eksponnecijalno F(N) je priblizno (1.618)^N Najveci fibonacijev broj koji se moze prikazati kao 32-bitni integer jest F(45)=1836311903 Zelimo li racunati F(N) za velike N mozemo implemetirati zbrajanje veliki pozitivnih cijelih brojeva. (Vidite zadatke u predavanju 9.) Mi cemo zbog jednostavnosti i jasnoce izlaganja ignorirati ovaj problem.

1. dobro rjesenje (ne koristimo rekurziju!).


int fibonaci(int N){ int f0=1; int f1=1; int i, pom; if(N==0) return f0; if(N==1) return f1; for(i=2; i <= N; i++){ pom=f0; f0=f1; f1+=pom; } return f1; }

Ocigledno slozenost ovog algoritma je ocigledno linearna O(N).

2. lose rjesenje (Koristimo rekurziju na los nacin, malo kasnije cemo upoznati dobro rekurzivno rjesenje!).


int fibonaci(int N){ if(N==0) return 1; if(N==1) return 1; return fibonaci(N-1)+fibonaci(N-2); }

Kod izgleda vrlo kompaktan i citljiv, ali je izuzetno neefikasan. Gornja implementacija pokazuje da je slozenost algoritma O(F(N)) tj. O((1.618)^N) sto je eksponencijalna slozenost i to je naravno ne prihvatljivo.

Zasto je slozenost O(F(N))? Odgovor:

Linija koda return fibonaci(N-1)+fibonaci(N-2); pokazuje slozenost(N)=slozenost(N-1)+ slozenost(N-2)+3, gdje u svakom funkcijskom pozivu imamo dva usporedjivanja (N==0 i N==1), jedno zbrajanje te slozenost koja dolazi od racunja F(N-1) i F(N-2). Odatle dobivamo trazenu slozenost. Rijesite sami ovu nelinearnu rekurzivnu jednadzbu drugog reda!

Neefikasnot ovog rjesenja ima i svoje intuitivno objasnjenje koje se dobije kada pratimo ugnijezdene fukcijske pozive.


Odredjujemo 6-ti clan fibonacijevog niza. 1. Racunamo fibonaci(5) za odredjivanje 6-tog fibonacijevog broja. 2. Racunamo fibonaci(4) za odredjivanje 6-tog fibonacijevog broja. 3. Racunamo fibonaci(4) za odredjivanje 5-tog fibonacijevog broja. 4. Racunamo fibonaci(3) za odredjivanje 5-tog fibonacijevog broja. 5. Racunamo fibonaci(3) za odredjivanje 4-tog fibonacijevog broja. 6. Racunamo fibonaci(2) za odredjivanje 4-tog fibonacijevog broja. 7. Racunamo fibonaci(2) za odredjivanje 3-tog fibonacijevog broja. 8. Racunamo fibonaci(1) za odredjivanje 3-tog fibonacijevog broja. 9. Racunamo fibonaci(1) za odredjivanje 2-tog fibonacijevog broja. 10. Racunamo fibonaci(0) za odredjivanje 2-tog fibonacijevog broja. 11. Racunamo fibonaci(1) za odredjivanje 2-tog fibonacijevog broja. 12. Racunamo fibonaci(0) za odredjivanje 2-tog fibonacijevog broja. 13. Racunamo fibonaci(2) za odredjivanje 3-tog fibonacijevog broja. 14. Racunamo fibonaci(1) za odredjivanje 3-tog fibonacijevog broja. 15. Racunamo fibonaci(1) za odredjivanje 2-tog fibonacijevog broja. 16. Racunamo fibonaci(0) za odredjivanje 2-tog fibonacijevog broja. 17. Racunamo fibonaci(3) za odredjivanje 4-tog fibonacijevog broja. 18. Racunamo fibonaci(2) za odredjivanje 4-tog fibonacijevog broja. 19. Racunamo fibonaci(2) za odredjivanje 3-tog fibonacijevog broja. 20. Racunamo fibonaci(1) za odredjivanje 3-tog fibonacijevog broja. 21. Racunamo fibonaci(1) za odredjivanje 2-tog fibonacijevog broja. 22. Racunamo fibonaci(0) za odredjivanje 2-tog fibonacijevog broja. 23. Racunamo fibonaci(1) za odredjivanje 2-tog fibonacijevog broja. 24. Racunamo fibonaci(0) za odredjivanje 2-tog fibonacijevog broja. Rezultat:13

2. Strategije u radu sa rekurzijama

Dvije osnovne metode u radu sa rekurzijama su divide and conquer i dynamic programming.

3. Zadaci za vjezbu

1. Napisi te rekurzivnu funkciju koja implementira racunanje faktorijela. Napisite i nerekurzivnu varijantu.

2. Implementirajte rekurzivno racunaje Fibonacijevih brojeva koristeci top-down dinamicko programiranje.

3. Napisite rekurzivni program koji racuna izraze u postfiks obliku. Nacrtajte i stablo kao za prefiks oblik.

4. Napisite rekurzivni program za pretvaranje infiks oblika u postfiks.

5. Napisite rekurzivni program za pretvaranje postfiks oblika u infiks.

6. Koristeci bottom-up dinamicko programiranje, izracunajte izraz dan rekurzivno

C(N)=N+(1/N)∑(C(k-1)+C(N-k)) (sumira se po k, 1≤k≤N), N≥1 C(0)=1

7. Napisite program koji racuna binomne koeficijente koristeci top-down dinamicko programiranje. Uputa: Ako c(n, k) oznacava broj nacina da se izmedju n elemenata izabere k tj. "binomni koeficijent n povrh k", onda vrijedi c(n,k)=c(n-1, k)+c(n-1, k-1), c(n,n)=c(n,0)=1.

8.* Napisite rekurzivni program koji racuna izraze u infiks obliku. Pretpostavite da imate dovoljno zagrada.