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

;