Rekurzija


Naziv "Rekurzija" potiče od latinske reči "recurrere" (re - nazad, currere - izvršavati).

Rekurzija je metod rešavanja problema koji uključuje rastavljanje problema na manje potprobleme, sve dok se ne dođe do dovoljno malog problema koji se može trivijalno rešiti.

Rekurzivne funkcije su funkcije koje pozivaju same sebe. One omogućavaju lako i razumljivo rešavanje problema koji su po prirodi stvari rekurzivni.
Nekoliko primera rekurzivnih definicija:
         Faktorijeli:     n! = n ∙ (n–1)! ,    (n > 0),     0! = 1
         Fibonačijevi brojevi:     fn = fn-1 + fn-2 ,    (n > 1),     f1 = 1,     f0 = 0

Primer 1: Program računa zbir prvih n prirodnih brojeva koristeći rekurzivnu funkciju.
               (rekurzivni_zbir(5) = 5 + 4 + 3 + 2 + 1 = 15)

 				
def rekurzivni_zbir(n):
	if n == 1:			#Ako je uneti broj n = 1, funkcija vraća 1,
		return n 		#tj. rekurzivni_zbir(1) = 1
	else: 
		return n + rekurzivni_zbir(n-1)
					
print (rekurzivni_zbir(5))	#Štampa se rezultat funkcije
				
Kopiraj


Ako pozovete funkciju rekurzivni_zbir(n), Pajton prevodilac će uraditi sledeće:

rekurzivni_zbir(5)
= 5 + rekurzivni_zbir(4)
= 5 + (4 + rekurzivni_zbir(3))
= 5 + (4 + (3 + rekurzivni_zbir(2)))
= 5 + (4 + (3 + (2 + rekurzivni_zbir(1))))
= 5 + (4 + (3 + (2 + 1)))
= 15
			


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.

;