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:

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)

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).

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.

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))

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))

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))