Mikor érdemes rekurziót használni?

Jobbára akkor, ha előre nem tudni, hogy hány alkalommal kell majd meghívni ugyanazt a függvényt.

Mondjuk egy parser építésénél.

van amit egyszerűbb rekurzívan megírni, pls quicksort, hatványozás, fibonacci...

Minden rekurzív függvényt meg lehet írni iteratívan is, csak legtöbb esetben bonyolítja a kódot.

Rekurzívnak a hátránya, hogy könnyebben lesz stackOverflow.

Általában a rekurziót ciklussal lehet helyettesíteni (vagy veremmel, sorral) és sokszor érdemes is, hiszen a rekurzió sokkal több memóriát emészt fel.

Persze van néhány eset, amikor rekurziót használnak, pl egy bináris fa bejárása.

Ebből ugye az következik, hogy elvileg nem érdemes használni, de látványos, érdekes és sokszor "leegyszerűsít" egy-egy algoritmust.

[link]

pl Recursive Backtracking

sodoku, labirintus generálás stb

"pl egy bináris fa bejárása."

Vagy bármilyen fa, pl. tipikus példa a könyvtárszerkezet bejárása.

Olyankor célszerű (általában), amikor a feldolgozandó adatstruktúra (eseménytér, stb.) hasonló felépítésű, mint a részelemei, tehát a részek ugyanazt a mintát követik, mint az egész. A faktoriális, fibonacci, stb. pl. pont ilyenek.

Viszont nagyon fontos megnézni, hogy így milyen hatékonyan végezhető el a feladat. Suliban volt egy feladat, már nem emlékszem, valami sorozat számítás rekurzívan. Elég jó képességű gépek voltak, de olyan eszement rekurzív algoritmust kellett implementálni, hogy 10-15-ös paraméter esetén a függvény már 5-10 másodpercig ketyegett, 20-as körül meg teljesen beállt (nem vártuk ki, amíg lefut.) Szóval meg kell nézni, van amikor rekurzívan érdemes, és van, amikor nagyon nem éri meg.

pl a fibo rekúrzív megoldása pont ilyen

a fibo(10) az már több mint 100 függvényhívás