Fibonačijev niz


Fibonačijev niz je niz brojeva u kome su prva dva broja 0 i 1, a svaki sledeći je zbir prethodna dva broja:

0, 1, 1, 2, 3, 5, 8, 13, 21,…

rekurzija5.jpg

Primer 6: Program za izračunavanje Fibonačijevog broja preko rekurzije.

Sada će biti dva bazna slučaja: f(0) = 0 i f(1) = 1, a rekurzivni korak će biti: f(n-1) + f(n-2) = f(n)

 				
def fib(n):
    if n == 0 or n == 1:	#bazni slučaj
        return n
    else:				#rekurzivni korak
        return fib(n-1) + fib(n-2)
Kopiraj

Prilikom pozivanja funkcije fib(4), prvo se proverava da li je argument jednak nuli ili jedinici. Ako nije, nastavlja dalje i poziva funkciju fib(4-1) i fib (4-2), tj. fib(3) i fib(2). Na ovaj način se rekurzivno poziva funkcija dok sve funkcije fib ne dođu do baznog slučaja. Zatim se sve funkcije izračunavaju „ka gore“ dok se ne dođe do prve pozvane funkcije – fib(4) i kada će se konačno dobiti traženi rezultat – 3.


Radi preglednijeg prikaza, umesto funkcije fib(n) pisano je F(n).

rekurzija6.gif

Na sledećoj animaciji se može uvideti mana rekurzivnog načina izračunavanja Fibonačijevog broja. Prilikom razlaganja problema na manje potprobleme dolazi do preklapanja potproblema i do višestrukih poziva istih funkcija što je memorijski i vremenski dosta zahtevno.

rekurzija7.gif


Iterativni i rekurzivni način za izračunavanje Fibonačijevog broja



Iterativni način:

 				
def fib(n):
    a = 0	#Prvi element
    b = 1	#Drugi element
    suma = 0 #Zbir prethodna dva elementa
    for i in range(n):
        suma = a + b
        a = b
        b = suma
    return a
	
print (fib(5))
Kopiraj

Rekurzivni način:

 				
def fib(n):
    if n == 0 or n == 1:	#bazni slučaj
        return n
    else:		#rekurzivni korak
        return fib(n-1) + fib(n-2)

print (fib(5))
Kopiraj



Vežba: Napisati rekurzivni program za stepenovanje dva prirodna broja.

Rešenje:

 				
def rstepen_sporo(x, n):
    if n == 0:
        return 1
    else:
        return x * rstepen_sporo(x, n-1)
    
print (rstepen_sporo(2, 4))
Kopiraj
levo desno

Uputstvo

Neke od programa nećete moći da pokrenete na našoj konzoli, zato Vam predlažemo da sa zvaničnog sajta www.python.org preuzmete portabilnu verziju. Instalacija je vrlo jednostavna. Mi Vam predažemo da odaberete verziju 3.3.5 koju smo i mi koristili. Tekstualni editor u kome možete pisati svoje programe se pokreće preko programa koji se zove IDLE i automatski se instalira sa celim paketom. Novi program započinjete klikom na padajući meni "FILE" >> "NEW FILE". Možete ga pokrenuti pritiskom na dugme F5 na tastaturi.
Konzola koja se nalazi na sajtu omogućava rad sa većinom prezentovanog materijala, ali je naglašeno kada je potrebno preći na instaliranu konzolu.

;