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)

Korišćenje rekurzije nad stringovima


Palindromi su smislene rečenice i reči koje se isto čitaju i sa leve i sa desne strane.

Primer 4: Program koji ispituje da li je neka reč palindrom.

 				
def da_li_je_palindrom(rec):
    #sva slova se prebacuju u mala radi boljeg upoređivanja
    rec = rec.lower() 	
        #ako se reč sastoji od jednog ili dva slova, ona je palindrom
    if len(rec) == 1 or len(rec) == 0:		#bazni slučaj
    	return True	
    else:				#rekurzivni slučaj
                #proverava se prvo i poslednje slovo		
	if rec[0] == rec[-1]:
            return da_li_je_palindrom(rec[1:-1]) 	#koristi se isecanje reči
        else:
            return False

print (da_li_je_palindrom("zdravo"))	#program ispisuje „False“
print (da_li_je_palindrom("radar")) 	#program ispisuje „True“
print (da_li_je_palindrom("Teret"))	#program ispisuje „True“
print (da_li_je_palindrom("dovidjenja")) #program ispisuje „False“
Kopiraj

Program da_li_je_palindrom prvo prebacuje sva slova u mala kako bi se izbeglo upoređivanje malih i velikih slova. U baznom slučaju se proverava da li je reč dužine nula ili jedan i ako jeste, program vraća „True“, a ako nije, nastavlja se dalje ka rekurzivnom slučaju. U rekurzivnom slučaju se proverava da li je prvo i poslednje slovo isto i ako je isto, ponovo se poziva funkcija, ali ovog puta se proverava reč iz koje je izbačeno prvo i poslednje slovo (koristi se isecanje - rec[1:-1]). Ova rekurzija se ponavlja ili dok se ne skrati reč na dužinu jedan ili dok se ne uporede dva različita slova.

rekurzija3.gif

Primer 5: Program za ispisivanje reči unazad.

 				
def okreni(rec):
    if len(rec) <=  1:
        return rec
    else:
        return okreni(rec[1:])  +  rec[0]

print (okreni("zdravo"))
Kopiraj

Program radi sledeće:

 				
okreni("zdravo")
= okreni("dravo") + z
= okreni("ravo") + d + z
= okreni("avo") + r + d + z
= okreni("vo") + a + r + d + z
= okreni("o") + v + a + r + d + z	#osnovi uslov kada je reč dužine 1
= o + v + a + r + d + z
= ovardz

Vežba: Proveriti šta će se desiti ako se u rekurzivnom koraku zameni redosled "okreni(rec[1:]) + rec[0]" sa "rec[0] + okreni(rec[1:])"

Objašnjenje:
Program bi radio sledeće:

 				
okreni("zdravo")
= z + okreni("dravo")
= z + d + okreni("ravo") 
= z + d + r + okreni("avo")
= z + d + r +  a + okreni("vo") 
= z + d + r +  a + v + okreni("o")	#došli smo do osnovnog 
= z + d + r +  a + v + o			#uslova kada je reč dužine 1
= zdravo


Vežba: Napisati rekurzivni program koji za argument uzima listu brojeva i računa sumu svih elemenata te liste.

Rešenje:

 				
def suma_liste(lista):
   if len(lista) == 1:
        return lista[0]
   else:
        return lista[0] + suma_liste(lista[1:])

print (suma_liste([1,3,5,7,9]))
Kopiraj

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)

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

Kule Hanoja


Još jedan primer rekurzije je problem “kule Hanoja" koji je verovatno najpoznatiji rekurzivni problem u kompjuterskoj literaturi. Osnova problema su tri štapa A, B i C, koja su zabodena na ravnoj podlozi. Na jednom štapu, npr. na A, naslagano je n kolutova različitih prečnika poređanih po veličini tako da se najveći kolut nalazi na dnu, a najmanji na vrhu. Zadatak je preneti sve kolutove (jedan po jedan) s prvog na drugi štap. Postavlja se pitanje: Koliki je najmanji broj prenosa an potreban da se svih n kolutova prenese s prvog na drugi štap?

Pri prebacivanju kolutova treba poštovati sledeća pravila:

  • U jednom potezu dozvoljeno je premestiti samo jedan kolut.
  • Nije dozvoljeno staviti veći kolut preko manjeg.
  • Svaki od štapova može se koristiti za privremeno smeštanje kolutova. Može se npr. koristiti treći štap C za privremeni smeštaj kolutova, ali uz poštovanje prethodna dva pravila.

rekurzija8.gif

> > DODATAK: Legenda o kuli Hanoja

Legenda kaže da je pre mnogo godina,negde u okolini grada Hanoj, živeo car koji je tražio novog dvorskog mudraca.Pošto je i sam bio mudar, želeo je da pronađe što boljeg mudraca, pa je rešio da uzme onoga koji da najbolje rešenje postavljenog problema (zagonetke): Dato je tri štapa i n diskova različitog prečnika. Svi diskovi su postavljeni na prvom štapu tako da se uvek manji disk nalazi iznad većeg. Potrebno je prebaciti sve diskove sa izvornog štapa na ciljni, premeštajući jedan po jedan disk, koristeći treći štap kao pomoćni, ali da se ni u jednom momentu disk većeg prečnika ne nađe na disku manjeg prečnika. Mnogi mudraci iz cele zemlje dolazili su pred cara sa raznim rešenjima, ali su rešenja bila ili nerazumljiva ili predugačka. „Mora da postoji jednostavniji način“, razmišljao je car. Jednog dana je pred cara stigao Buda, i rekao da je problem toliko jednostavan da se rešava sam od sebe. Svoje rešenje Buda je izložio na sledeći način: 1. Ako postoji samo jedan disk, pomeramo ga sa izvornog na ciljni štap, i to je toliko jednostavan posao da ga može uraditi svaka seoska luda. 2. Ako pak ima više od jednog diska postupak je sledeći: premestimo prvo n-1 diskova sa izvornog na pomoćni štap, koristeći ciljni kao pomoćni. Pošto je n-1 diskova na pomoćnom štapu, a najveći je i dalje ostao na izvornom, problem se svodi na tačku 1), tj. treba prebaciti taj jedan disk sa izvornog na ciljni štap. Potom treba n-1 diskova, sa pomoćnog štapa prebaciti na ciljni po istom postupku (sada koristeći izvorni štap kao pomoćni). Kada je Buda završio sa pričom, car ga je pitao kada će konačno reći svoje rešenje. Buda se samo nasmešio i otišao.


Iterativno rešenje ovog problema je veoma kompleksno, a rekurzivno prilično jednostavno. Ukoliko je n = 1, prebaciti disk sa polaznog na dolazni štap, inače: prebaciti (rekurzivno) n-1 diskova sa polaznog na pomoćni štap (korišćenjem dolaznog štapa kao pomoćnog), prebaciti najveći disk sa polaznog na dolazni štap i, konačno, prebaciti (rekurzivno) n-1 diskova sa pomoćnog na dolazni štap (korišćenjem polaznog štapa kao pomoćnog).

rekurzija9.jpg
 				
#pomoćna funkcija koja štampa informaciju
def stampaj_korak(polazni, dolazni):   
    #sa kog štapa na koji štap se prebacio disk
    print ("Pomeri sa " + str(polazni) + " na " + str(dolazni)) 

#f-ja Kule za argumente uzima broj diskova i nazive štapova
def Kule(n, polazni, dolazni, pomocni):	
    if n == 1:	#bazni slučaj. Ako postoji samo jedan disk, izvršiti prebacivanje
        stampaj_korak(polazni, dolazni)
    else:		#rekurzivni korak
	#prvo se prebacuje n-1 diskova sa polaznog na pomoćni štap
        Kule(n-1, polazni, pomocni, dolazni)
	#najveći disk se prebaci sa polaznog na dolazni štap
        Kule(1, polazni, dolazni, pomocni)	 
	#na kraju, n-1 diskova se prebacuje sa pomoćnog na dolazni štap
        Kule(n-1, pomocni, dolazni, polazni)  

Kule(3, "A", "C", "B")
Kopiraj

Program će ispisati sledeće:

 				
Pomeri sa A na C	
Pomeri sa A na B
Pomeri sa C na B
Pomeri sa A na C
Pomeri sa B na A
Pomeri sa B na C
Pomeri sa A na C