Mért rossz a rekurzió?

Több helyet foglal a stacken, mert minden híváskor oda kerülnek a lokális változók. így könnyebben előfordulhat stack owerflow. Illetve lassabb is lehet, mint egy itaratív megoldás.

Persze nem minden rekurzív hívás "rossz", néha a fordító simán optimalizálja és ami látszólag rekurzív kód, az nem lesz az. Keress rá pl a tail-recursion optimization-ra.

Igen, kevesebb a tárhely igénye.

A rekurzív megoldásnak O(log N) tárhely kell, míg az iteratívnak csak O(1).

Nyilván mindjkettő csak akkor jó, ha helyes eredményt ad.

"Nem mindig egyértelmű, hogy a rekurzív algoritmus több memóriát foglal"

De, ez mindig egyértelmű, hiszen a rekurzív hívásnál legalább a visszatérési címet el kell tárolni. Ilyenre iteráció esetén nincs szükség.