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

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]

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)

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.

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)