Izračunavanje faktorijela


Primer 3: Program za izračunavanje faktorijela koji koristi rekurzivni poziv.

 				
#Pretpostavimo da je n pozitivan ceo broj
def fakt (n):
    if n == 0:	#bazni slučaj
        return 1
    else:
        return n * fakt(n-1)  #rekurzivni korak 

print (fakt(4))	#Štampa se rezultat funkcije
Kopiraj

Ako pozovete funkciju fakt(4), Pajton prevodilac će uraditi sledeće:

 				
fakt (4)
Prvi poziv = 4 * fakt(3)
Drugi poziv = 4 * 3 * fakt(2)
Treći poziv = 4 * 3 * 2 * fakt(1)
Četvrti poziv = 4 * 3 * 2 * 1 * fakt(0)
Peti poziv = 4 * 3 * 2 * 1 * 1 [Prva povratna vrednost iz petog poziva (1 * 1)]
= 4 * 3 * 2 * 1 [Druga povratna vrednost iz četvrtog poziva (2 * 1)]
= 4 * 3 * 2 [Treća povratna vrednost iz trećeg poziva (3 * 2)]
= 4 * 6 [Četvrta povratna vrednost iz drugog poziva (4 * 6)]
= 24 [Peta (poslednja) povratna vrednost iz prvog poziva]

rekurzija1.jpg

Pri ulasku u funkciju, argument n je 4. Funkcija proverava da li je n == 0 i ako jeste, funkcija vraća 1 (faktorijel od 0 je 1), a ako nije, funkcija dolazi do rekurzivnog koraka gde vraća 4 puta faktorijal od n-1 i ponovo poziva funkciju fakt ali ovog puta je argument n-1 = 3. Funkcija će na ovaj način pozivati samu sebe dok n ne postane 1. Tada funkcija zna koju vrednost treba da vrati (vraća 1) i onda se polako „penje gore“, množi sa 2, pa sa 3 i tako sve dok ne dodje do poslednjeg broja, tj. do broja sa kojim je funkcija pozvana u program


Da bi se videlo šta se dešava u programu, koristi se print funkcija.

 				
#Pretpostavimo da je n pozitivan ceo broj.
def fakt (n):
    print ("Faktorijel je pozvan za broj n = " + str(n))
    if n == 0:
        print ("n = 0 : Faktorijel od 0 je 1")
        return 1
    else:
        rezultat = n * fakt (n-1)
        print ("n = %d : Rezultat za %d * faktorijel(%d) je %d"%(n, n, n-1, rezultat))
        return rezultat

fakt (4)
Kopiraj

Program će ispisati sledeće:

 				
Faktorijel je pozvan za broj n = 4
Faktorijel je pozvan za broj n = 3
Faktorijel je pozvan za broj n = 2
Faktorijel je pozvan za broj n = 1
Faktorijel je pozvan za broj n = 0
n = 0 : Faktorijel od 0 je 1
n = 1 : Rezultat za 1 * faktorijel(0) je 1
n = 2 : Rezultat za 2 * faktorijel(1) je 2
n = 3 : Rezultat za 3 * faktorijel(2) je 6
n = 4 : Rezultat za 4 * faktorijel(3) je 24

Prilikom svakog poziva funkcije u stek segmentu memorije stvara se novi stek okvir - stek okvir za novu instancu funkcije fakt. U ovim stek okvirima lokalna promenljiva n imaće redom vrednosti 4, 3, 2, 1, 0. Sve instance funkcije fakt koriste isti primerak koda funkcije fakt (koji se nalazi u kod segmentu). Stek okvir svake instance funkcije fakt ,,pamti“ dokle je ta instanca funkcije stigla sa izvršavanjem koda (kako bi izvršavanje moglo da bude nastavljeno od te tačke kada ta instanca funkcije ponovo postane aktivna). Kada se vrši povratak iz funkcije u pozivajuću rutinu, parametri poziva se skidaju sa steka.

rekurzija2.jpg
rekurzija4.gif


Vežba: Napisati rekurzivni program za računanje proizvoda dva broja znajući da je, npr., 4*a = a + a + a + a = a + 3*a

Rešenje:

 				
def rekurzivno_mnozenje(a, b):
    if b  == 1:
        return a
    else:
        return a +  rekurzivno_mnozenje(a, b-1)

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.

;