Dobre i loše strane rekurzije


Dobre strane rekurzije su (obično) čitljiv i kratak kod, jednostavan za razumevanje. Dakle, može se naići na problem koji je jako teško rešiti iterativno i zahteva veliki programerski napor, dok je rekurzivno rešenje tog istog problema mnogo jednostavnije i ne zahteva veliki programerski napor. Primer ovakvog slučaja su „Kule Hanoja“ koje će kasnije biti obrađene.


Loše strane rekurzije:

Cena poziva: Prilikom svakog rekurzivnog poziva kreira se novi stek okvir i kopiraju se argumenti funkcije. Kada rekurzivnih poziva ima mnogo, ovo može biti veoma memorijski i vremenski zahtevno, te je poželjno rekurzivno rešenje zameniti iterativnim. Primer ovakvog slučaja je program za izračunavanje Fibonačijevog broja.

Suvišna izračunavanja: U nekim slučajevima prilikom razlaganja problema na manje potprobleme dolazi do preklapanja potproblema i do višestrukih rekurzivnih poziva za iste potprobleme.


Opšte pravilo je da, ako se neki problem lako rešava iterativno, onda treba da se radi iterativno. Rekurzivno rešenje treba da se usvoji samo ako iterativno rešenje traži preveliki programerski napor. Teorijski, svaki problem može da se rešava iterativno.