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)
Kopiraj

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

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.

;