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:     f_n = f_n-1 + f_n-2 ,    (n > 1),     f₁ = 1,     f₀ = 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
				

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