Milyen dolgok kiszámításához érdemes rekurziót használni?

Én azt mondom, semmihez. Kicsit megerőszakolása a memóriának. Beágyazott rendszerekben be is van tiltva általában.

Amúgy amihez szükséges lehet, az például egy bináris fa kezelése. De bináris fát tárolni sem nagyon szoktak, nem éppen könnyen kezelhető szerkezet.

Nekem van egy olyan térképem, ami mozaikokból áll.

Minden mozaik ismeri a szomszédait.

Ennek a kijelzéséhez ideális a rekurzió.

Elindulok az "Ön itt áll" pontról, aztán jönnek a szomszédok.

Minden szomszéd ugyanígy működik.

Tetszőleges formájú, akár lyukas térképet is ki tud jelezni.

Több szempont is szerepet játszik/játszhat:

Erőforrásigényesség

Az hogy erőforrásigényesebb-e és ha igen mennyivel a rekurzív megoldás az az adott esetben a rekurzív és nem rekurzív implementáció alapján a konkrét végrehajtott bájtkódok elemzései alapján lehet megmondani a legpontosabban.

Melyiket egyszerűbb , melyiket gyorsabb implenetálni

Nem minden esetben a rekurzív megoldást egyszerűbb implenetálni.

Rendelkezésre áll e elég hardver erőforrás

Lehetséges hogy az egyikre igen a másikra nem az adott hardveren, de az is lehet hogy mind a kettő implenetáció szerint elfut.

Futási idő különbség:

Ez számít e? Nem biztos, ezred vagy század másodpercen múlik és felhasználói felületen ezen hozzáadott időkülönbség és egyébként elég hardver erőforrás van rá akkor ez nem szempont hogy rekurzív vagy nem a futási idő szempontjából. Persze valós idejű rendszernél ez fotons lehet.

Hányszor kell lefuttatni? Ha csak 1x és futási időben 1 másodperc, de implenetációban meg fél óra akkor összességében mégiscsak azt értemes amelyik gyorsabb impelentálni.

A teljesség igénye nélkül csak általánosságban nem mindig számít még az se ha 2x lassabb is lenne, ez attól függ.

"Én azt mondom, semmihez. Kicsit megerőszakolása a memóriának. Beágyazott rendszerekben be is van tiltva általában."

Csak mellesleg megjegyzem, hogy például gcc és a g++ compilernek kismillió kapcsolója van melyek alapján beparaméterezhető a fordítás, még adott esetben a függvényhívás függvényhíváson belül is úgy fordítja mintha nem történne külön függvényhívás, képes csómó optimalizációra, az asm kiementet lehet tanulmányozni, olvasmányosabb mint a natív gépi kód, de izomorf vele. Statikus kódelemzés, egyebek bele lehet menni, de általában nem ezen múlik hogy elég jól optimalizált e az adott célra.

"Amúgy amihez szükséges lehet, az például egy bináris fa kezelése. De bináris fát tárolni sem nagyon szoktak, nem éppen könnyen kezelhető szerkezet."

A bináris fa, legalábbis a bináris mintafa az az a fa amiben nincs semmi kiegyensúlyozó algortimus, az semmi már ha a nehézségéről beszélünk. Az könnyen torkollhat elfajuló fává, kvázi mintha láncolt lista lenne. Ha viszont az a bináris fa egy AVL fa, annak már igen komoly önkiegyensúlyozó algortimusa van. Cserébe minden beszúrási művelet garantáltan legfeljebb ordó log n (ahol n a fa elemszáma), minden törlés is és minden elem keresés is. A fa magassága legrosszabb esetben sem lehet több mint gyök 2 -szöröse több mint ami legoptimálisabb esetben lehetne.

Ha egy lista adatszerkezetünk van amely egy tömb adatszerkezetre épül, akkor legrosszabb esetben egy beszúrási művelet az új elem felvétele az összes többi régi elem átmásolása az új tömbbe, a régi tömb megszüntetése, azaz ordó n futási idejű. Ezzel szemben egy AVL fában ordó log n legrosszabb esetben is egy beszúrási művelet.

Még továbbá ha már itt tartunk érdemes megemlíteni az alapvetően nem a nem operatív memóriára tervezett adatszerekezetek közül (háttértárra tervezték) a B-fát, ahol nem mindig 2 fele ágazhat a fa, hanem sok fele például 16 fele (de ez paraméterezhető) és ráadásul az önkiegyensúlyozó algortumus bele van építve ami az AVL vagy a piros fekete fák általánosításának is tekinthető. Ahol a keresési, törlési, beszúrási idő legrosszabb esetben is garantáltan ordó log n. Azért nem mindegy ha van 10 milliárd elemed és legrosszabb esetben mind a 10 milliárdon végig kell menned ha keresed vagy pedig ennek valahanyad alapú logaritmusa keresési lépés alatt megtehető legrosszabb esetben is. Erre már tényleg azt mondom hogy elég kompikált összetett algorimtus ami alapján ez megy, de ezt elvégzi a back-end rendszer/api/keretrendszer/modul (bárhogy is nevezzük) implenetációja. Mivel gyakorlatba nem úgy van mint az oviba mint amit tanítottak, hogy minden algoritmust magunknak kell implenetálni. Az alapvető algoritmusokat magunktól is tudni kell implementálni, annyi rutinnal rendelkezni kell azért tanítják. Viszont ez is mint a B-fák így nyersen nem fogalkozunk velük a gyakorlatban általában, ez jellemzően egy sql adatbázis elvégzi helyettünk a nélkül hogy külön végig gondolnánk. Az kell hogy e szerint indexeklni szükséges e, ha igen akkor beállítjuk és a háttérben tárolva lesz hozzá b-fa. Ha valami elsődleges kulcs a háttérbe az is b-fa lesz.

C++-ban meg az asszociatív tömb mint map nevű template AVL fával van implenetálva. Python-ban a dict mint asszociatív tömb pedig hasítótáblával van impelentálva, de van külön telepíthető modul hozzá mely szintén önkiegyensúlyozó fán alapul ... stb.