Ha egy implementáció során iteráció és rekurzió közül kell választanotok, melyiket választjátok?

Kikapcsolt optimalizációnál mégis miért optimalizálná?

C++ kódba pedig faktoriálist 2017-ben nem számolják futás közben:

constexpr int faktorialis_recursive(int n) {

if (n <= 1) {

return 1;

}

return n * faktorialis_recursive(n - 1);

}

constexpr auto get_factors() noexcept {

std::array<int, 13> arr{};

for (std::size_t i = 0; i < arr.size(); ++i) {

arr[i] = faktorialis_recursive(i);

}

return arr;

}

constexpr auto factors = get_factors();

A jobbrekurzív függvényeket (tail recursion) kb minden ismert fordító automatikusan ciklussá alakítja, így az nem eszi meg a stacket. Amennyiben a rekurzió elegánsabb, jobban átlátható megoldás, csak akkor nem választom azt a megoldást imperatív nyelvek estén, hogyha a függvényem nem jobbrekurzív és rekuziók száma nem korlátos. Általában a ciklusos megoldás az optimálisabb, de még a nem jobbrekurzív függvények esetén is a különbség nagyon minimális.

(btw a lokális változók definiálása és a függvényhívások a stack pointer mozgatásával járnak és nem memóriafoglalással)

"btw a lokális változók definiálása és a függvényhívások a stack pointer mozgatásával járnak és nem memóriafoglalással"

A stack is memóriát foglal. Rekurzió esetén pedig n-szer x változóterület kerül foglalásra.

Stack overflow. Gondolom ismerős.

Ahogy már az első válaszoló megírta, az feladattól függ. De hogy lássál is rá példát, ahol tényleg számít, vegyük a Fibonacci számokat és legyen a feladat kiszámolni az n-edik Fibonacci számot. Ilyenkor ha a rekurzívan írod meg a függvényedet, azaz F(n)=F(n-1)+F(n-2) az nagyon gyorsan el fog szállni mind memória, mind futásidőben. Ellenben ha egymás után számolod ki őket for ciklussal, akkor nagyon gyorsan kijön az eredmény és csak 2 számnak kell helyet foglalni.

Ezzel szemben vegyük a DFS gráfbejárást. Ott kb. ugyanúgy teljesít az algoritmus, ha iteratívan vagy rekurzívan írod meg, de mivel a rekurzív módszer tömörebb és elegánsabb, ezért célszerűbb azt használni.

Én általában csak akkor írok rekurziót, ha oltári nagy szopással jár az iteratív módszer. A faktoriálisos példádnál meg az a sanda gyanúm, hogy a rekurzív módszert nem unrollolja a compiler, bár ezt csak akkor érdemes figyelembe venni, ha számít az a pár milliszekundum.