Imam jedan zadatak. Rekao bih da je više matematički, nego informatički.
Algoritam glasi

Kôd: Obeleži sve

def fibonacci(n):
 if n == 0 or n == 1:
 return 1
 else:
 return fibonacci(n - 1) + fibonacci(n - 2)

Traži se [inlmath]n[/inlmath]-ti član Fibonačijevog niza.
Naredba return izlazi iz funkcije i prebacuje tok izvršavanja na funkciju u okviru koje je pozvana istovremeno vraćajući određenu vrednost.
Algoritam je rekurzivan i nadam se da je jasan.
Merimo efikasnost na sledeči način. Ukoliko nije ispunjen uslov, izvršavaju se [inlmath]4[/inlmath] komande (provera u uslovu, dva rekurzivna poziva i operacija sabiranja). A ukoliko je uslov ispunjen (to će se desiti kada dođemo do funkcija sa argumentom 0 ili 1), imamo [inlmath]2[/inlmath] komande (proveru uslova i naredbu return).
Ja sam ovako započeo:
Neka je [inlmath]n[/inlmath] neki veliki broj tj. tražimo član u nizu sa veoma velikim indeksom.
Imamo:
[inlmath]f(n)=4+f(n-1)+f(n-2)[/inlmath]
Kada pozovemo prvi put ovu funkciju za to veliko [inlmath]n[/inlmath], izvršiće se one [inlmath]4[/inlmath] instrukcije. Dalje razlažemo [inlmath]f(n)=4+\bigg(4+f(n-2)+f(n-3)\bigg)+f(n-2)[/inlmath]
U primerima koje smo radili, dovoljno je razložiti još malo i uočiti neku pravilnost. Ovde nikako ne mogu da dokučim posle koliko koraka dolazimo do funkcija sa argumentima 0 ili 1, Takođe, ne znam kako da odredim koliko imamo ovih rekurzivnih funkcija u kojima će se izvršiti ove [inlmath]4[/inlmath] operacije (broj tih funkcija bi trebao da se izrazi preko [inlmath]n[/inlmath]).
Jasnije će biti sa slike o čemu se radi, iako nije baš neko umetničko delo . Ukoliko uzmemo da je [inlmath]n=5[/inlmath] imaćemo [inlmath]7[/inlmath] funkcija koje će izvršiti po [inlmath]4[/inlmath] operacije (obeležene crvenom bojom), i one koje će izvršiti dve operacije (obeležene crnom). Ovde možete videti principe rešavanja na jednostavnijim primerima, ukoliko nisam nešto objasnio kako treba.

Objašnjenje je malo opširnije, jer se verovatno niste susretali sa ovakvim tipom zadatka.

Ako sam dobro razumeo šta je problem, ti zapravo ovde treba da izraziš [inlmath]f(n)[/inlmath] u funkciji od [inlmath]n[/inlmath], a to postižeš tako što ćeš rešiti nehomogenu linearnu diferencnu jednačinu drugog reda,
[dispmath]f(n)-f(n-1)-f(n-2)=4[/dispmath]
Da li znaš postupak njenog rešavanja? (Ukratko, nađeš rešenja odgovarajuće homogene jednačine pomoću karakteristične jednačine, zatim nađeš partikularno rešenje i na kraju ta dva rešenja sabereš.)
Ako treba da pokažem detaljniji postupak, reci.
Uglavnom, ako sam dobro razumeo da su početni uslovi [inlmath]f(0)=f(1)=2[/inlmath], onda treba da se dobije
[dispmath]f(n)=3\cdot\frac{5-\sqrt5}{5}\left(\frac{1-\sqrt5}{2}\right)^n+3\cdot\frac{5+\sqrt5}{5}\left(\frac{1+\sqrt5}{2}\right)^n-4[/dispmath]
što bi, uvrštavanjem različitih vrednosti za [inlmath]n[/inlmath], dalo
[dispmath]\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline
f(n) & 2 & 2 & 8 & 14 & 26 & 44 & 74 & 122\\ \hline
\end{array}[/dispmath]

Ovo se lako resava kad se postavi rekurentna jednacina. Odredjivanje vremenske slozenosti rekurzivnih funkcija se najlakse odredjuje resavanjem odredjene rekurentne jednacine. Kako je ovo fibonacijev niz resenje njegove rekurentne jednacine je
[dispmath]a_n=\frac{1}{\sqrt5}\Big(\frac{1+\sqrt5}{2}\Big)^n-\frac{1}{\sqrt5}\Big(\frac{1-\sqrt5}{2}\Big)^n[/dispmath]
Imamo da [inlmath]\frac{1}{\sqrt5}\Big(\frac{1-\sqrt5}{2}\Big)^n\in O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)[/inlmath] pa:
[dispmath]\frac{1}{\sqrt5}\Big(\frac{1+\sqrt5}{2}\Big)^n-O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)=O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)+O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)=O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)[/dispmath]
Tako da je gornja procena vremenske slozenosti ove funkcije [inlmath]O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)[/inlmath]. A prostorna (memorijska) je [inlmath]O(n)[/inlmath] jer uvek ima najvise [inlmath]n[/inlmath] stekova za funkciju u svakom trenutku.

I da se dopunim zbog nepreciznosti, nema [inlmath]n[/inlmath] stekova vec [inlmath]n[/inlmath] memorijskih lokacija na steku dodeljenih funkciji.

Da se dopunim i ja. Izraz za [inlmath]f(n)[/inlmath],

Daniel je napisao:[dispmath]f(n)=3\cdot\frac{5-\sqrt5}{5}\left(\frac{1-\sqrt5}{2}\right)^n+3\cdot\frac{5+\sqrt5}{5}\left(\frac{1+\sqrt5}{2}\right)^n-4[/dispmath]

može se, nakon razvoja stepena binoma i nešto sređivanja, napisati i u sledećem obliku:

• za [inlmath]n[/inlmath] parno:
  [dispmath]f(n)=\frac{3}{2^{n-1}}\Biggl({n\choose0}+{n\choose1}+{n\choose2}5+{n\choose3}5+{n\choose4}5^2+{n\choose5}5^2+\cdots+{n\choose n-1}5^{n/2-1}+{n\choose n}5^{n/2}\Biggr)-4[/dispmath]
• za [inlmath]n[/inlmath] neparno:
  [dispmath]f(n)=\frac{3}{2^{n-1}}\Biggl({n\choose0}+{n\choose1}+{n\choose2}5+{n\choose3}5+{n\choose4}5^2+{n\choose5}5^2+\cdots+{n\choose n-1}5^{(n-1)/2}+{n\choose n}5^{(n-1)/2}\Biggr)-4[/dispmath]

a moglo bi se možda i dalje malo srediti, korišćenjem Paskalove formule [inlmath]{n\choose k-1}+{n\choose k}={n+1\choose k}[/inlmath]...

Daniel je napisao:Da li znaš postupak njenog rešavanja? (Ukratko, nađeš rešenja odgovarajuće homogene jednačine pomoću karakteristične jednačine, zatim nađeš partikularno rešenje i na kraju ta dva rešenja sabereš.)

Ne znam, prvi put čujem za ovu vrstu jednačina.

@Trougao, A kako si došao do ovoga?

Trougao je napisao:Ovo se lako resava kad se postavi rekurentna jednacina. Odredjivanje vremenske slozenosti rekurzivnih funkcija se najlakse odredjuje resavanjem odredjene rekurentne jednacine. Kako je ovo fibonacijev niz resenje njegove rekurentne jednacine je
[dispmath]a_n=\frac{1}{\sqrt5}\Big(\frac{1+\sqrt5}{2}\Big)^n-\frac{1}{\sqrt5}\Big(\frac{1-\sqrt5}{2}\Big)^n[/dispmath]

Miladin Jovic je napisao:Ne znam, prvi put čujem za ovu vrstu jednačina.

One su vrlo korisne (da ne kažem neophodne) kad hoćeš da na osnovu rekurentne formule dobiješ eksplicitni izraz za [inlmath]n[/inlmath]-ti član niza.
[inlmath]f(n)-f(n-1)-f(n-2)=4[/inlmath] je diferencna (rekurentna) nehomogena linearna jednačina drugog reda. Nehomogena jer na desnoj strani nemamo nulu (da imamo nulu bila bi homogena), linearna jer su koeficijenti uz [inlmath]f(n-k)[/inlmath] konstante, a drugog reda jer je [inlmath]f(n)[/inlmath] izraženo preko [inlmath]f(n-1)[/inlmath] i [inlmath]f(n-2)[/inlmath].
Neki opšti slučaj diferencne jednačine drugog reda bio bi [inlmath]c_0f(n)+c_1f(n-1)+c_2f(n-2)=\varphi(n)[/inlmath]. U našem slučaju je [inlmath]c_0=1,\;c_1=-1,\;c_2=-1,\;\varphi(n)=4[/inlmath].
Postupak dosta podseća na rešavanje nehomogenih diferencijalnih jednačina. Prvo nađemo rešenja odgovarajuće homogene diferencne jednačine, a nju dobijemo tako što na desnoj strani [inlmath]\varphi(n)[/inlmath] zamenimo nulom:
[dispmath]f(n)-f(n-1)-f(n-2)=0[/dispmath]
Za homogenu jednačinu [inlmath]c_0f(n)+c_1f(n-1)+c_2f(n-2)=0[/inlmath] karakteristična jednačina glasi [inlmath]c_0\lambda^2+c_1\lambda+c_2=0[/inlmath] (o čemu je i Trougao pisao u ovom postu, koji takođe preporučujem da pogledaš). Dakle, u ovom slučaju,
[dispmath]\lambda^2-\lambda-1=0[/dispmath]
Rešenja ove jednačine su
[dispmath]\lambda_{1,2}=\frac{1\pm\sqrt5}{2}[/dispmath]
Kada su rešenja karakteristične jednačine međusobno različita (kao što je ovde slučaj), tada opšte rešenje homogene jednačine ima oblik [inlmath]f_H(n)=A_1\lambda_1^n+A_2\lambda_2^n[/inlmath], gde su [inlmath]A_1[/inlmath] i [inlmath]A_2[/inlmath] konstante. Dakle,
[dispmath]f_H(n)=A_1\left(\frac{1-\sqrt5}{2}\right)^n+A_2\left(\frac{1+\sqrt5}{2}\right)^n[/dispmath]
Sada partikularno rešenje. Za slučaj [inlmath]\varphi(n)=\text{const}[/inlmath], partikularno rešenje je oblika [inlmath]f_P(n)=c_0[/inlmath]. Konstantu [inlmath]c_0[/inlmath] određujemo uvrštavanjem partikularnog rešenja u nehomogenu jednačinu:
[dispmath]\cancel{c_0}-\cancel{c_0}-c_0=4\quad\Longrightarrow\quad c_0=-4[/dispmath][dispmath]f_P(n)=-4[/dispmath]
Opšte rešenje polazne nehomogene jednačine će sada biti zbir opšteg rešenja homogene jednačine i partikularnog rešenja:
[dispmath]f(n)=f_H(n)+f_P(n)[/dispmath][dispmath]f(n)=A_1\left(\frac{1-\sqrt5}{2}\right)^n+A_2\left(\frac{1+\sqrt5}{2}\right)^n-4[/dispmath]
Koeficijente [inlmath]A_1[/inlmath] i [inlmath]A_2[/inlmath] određujemo iz zadatih početnih uslova. Naši početni uslovi su [inlmath]f(0)=2[/inlmath] i [inlmath]f(1)=2[/inlmath]:
[dispmath]f(0)=A_1+A_2-4=2[/dispmath][dispmath]f(1)=A_1\frac{1-\sqrt5}{2}+A_2\frac{1+\sqrt5}{2}-4=2[/dispmath]
čime dobijemo sistem od dve jednačine s dve nepoznate, [inlmath]A_1[/inlmath] i [inlmath]A_2[/inlmath]:
[dispmath]A_1+A_2=6[/dispmath][dispmath]A_1\frac{1-\sqrt5}{2}+A_2\frac{1+\sqrt5}{2}=6[/dispmath]
Rešavanjem ovog sistema dobije se
[dispmath]A_1=3\cdot\frac{5-\sqrt5}{5},\qquad A_2=3\cdot\frac{5+\sqrt5}{5}[/dispmath]
pa je konačno rešenje polazne nehomogene diferencne jednačine
[dispmath]\enclose{box}{f(n)=3\cdot\frac{5-\sqrt5}{5}\left(\frac{1-\sqrt5}{2}\right)^n+3\cdot\frac{5+\sqrt5}{5}\left(\frac{1+\sqrt5}{2}\right)^n-4}[/dispmath]

---

Možeš pokušati, radi vežbe, da na sličan način izvedeš formulu i za [inlmath]n[/inlmath]-ti član Fibonačijevog niza. Kreneš od rekurentne formule [inlmath]f(n)=f(n-1)+f(n-2)[/inlmath], uz početne uslove [inlmath]f(0)=0,\;f(1)=1[/inlmath] (ovde sad nemaš nehomogenu, već homogenu jednačinu). Za [inlmath]n[/inlmath]-ti član niza dobićeš upravo onaj izraz koji je Trougao naveo, za koji si pitao kako je došao do njega...

Daniel je odlicno napisao kako se dolazi do onog izraza. Svaku rekurzivno zadatu funkciju mozes predstaviti kao rekurentnu jednacinu. Pocetni uslovi [inlmath]a_0,a_1[/inlmath] su ti oni if-ovi tj sta vracaju. Ako te vise interesuju i rekurentne jednacine i slozenost algoritama savetovao bih te da skines sa interneta knjigu Programiranje 2 od Predraga Janicica i Filipa Marica(nju smo koristili za programiranje 2 na fakultetu). Profesor Janicic ju je objavio na svom sajtu. Knjiga nije jos do kraja zavrsena ali ima deo sa kompleksnoscu algoritama i raznim tipovima rekurentnih jednacina i njihovim resenjima. Ima i sajt od prosle godine za programiranje 2 koji su nastavnici MATF-a napravili za studente brisu sadrzaj tek u decembru ili januaru pa postavljaju novi kad pocne prolecni semestar i krene nova grupa www.programiranje2.matf.bg.ac.rs.