Tri pravila rekurzije

Pravila pisanja rekurzivnog algoritma:

1.  Rekurzivni algoritam mora da ima BAZNI SLUČAJ (base case)
2. Rekurzivni algoritam mora da menja svoje stanje i da napreduje ka osnovnom slučaju – REKURZIVNI KORAK ili REKURZIVNI SLUČAJ (recursive case)
3.  Rekurzivni algoritam mora da zove samog sebe.

Bazni slučaj je slučaj u kojem problem može da se reši bez dalje rekurzije, tj. to je slučaj koji omogućava algoritmu da prestane sa rekurzijom (izlazni kriterijum). Obično je to dovoljno mali problem koji se može rešiti direktno (trivijalno).

U prethodnom primeru (Primer 1), bazni slučaj je bio:

 				
if n == 1:
	return n
		

a rekurzivni korak:

 				
else:
    return n + rekurzivni_zbir(n-1)

	

Ukoliko bi se izostavio bazni slučaj, rekurzivna funkcija bi pozivala samu sebe beskonačan broj puta što bi dovelo do preopterećenja i pucanja programa.

Primer 2: Loš primer rekurzivne funkcije (beskonačna rekurzija):

 				
def brojac(broj):
    print (broj)
    broj += 1
    brojac(broj)

Pošto nema baznog slučaja, odnosno izlaznog kriterijuma, ovaj program bi se na nekim kompajlerima izvršavao u beskonačost.