Mit nevezünk iteratív és mit rekurzívnak?

Beginpro
Mit nevezünk iteratív és mit rekurzívnak?
2011-01-01T10:10:27+01:00
2011-01-02T16:49:40+01:00
2022-07-24T20:16:29+02:00
  • Köszönöm a válaszokat!
    Mutasd a teljes hozzászólást!
  • Nagyon leegyszerűsítve:

    Iteráció:
    Egy olyan folyamat egy lépése, amely a célját egy algoritmus többszöri, egymás utáni lefutásával éri el. Általában minden lépés után közelebb jutunk az eredményhez. Nem kel hogy köze legyen a rekurzióhoz.
    Jó példa rá mondjuk a Newton módszer, valószinűleg középiskolában tanultál is róla - lehet hogy még oldottatok is meg egyszerű, nem lineáris egyenletrendszereket így.
    Mutasd a teljes hozzászólást!
  • Nincs olyan pont a hatályos magyar jogban (az EU jogot is ideértve), ami hivatalosan definiálná a rekurziót. A lényeg pont az, amit mondtál: rekurzív az, ami önmagát részként tartalmazza; például a fa rekurzív adatszerkezet (valamilyen alaptípust felvéve):

    fa = üres_fa vagy fa = (elem: alaptípus, baloldali-rész: fa, jobboldali-rész: fa)
    Mutasd a teljes hozzászólást!
  • Elméletileg iteratív az az algoritmus, amely bár az eredményt önmaga újbóli és újbóli végrehajtásával szolgáltatja, de az újabb futási menetek bemenetét szigorúan mindig az előző futási menetek kimenetei (eredményei) képezik. Ez azt jelenti, hogy maga az algoritmus belső állapotát sosem kell megőrizni, és annak csak teljes végrehajtását - és ezzel az adot futási menet eredményének előállását - követően kerülhet sor a következő futási menet megnyitására. Tipikus iteratív (ill. iterációval effektívebben megoldható) algoritmus pl. a Fibonacci sor generálása, a faktoriálisszámítás és a buborékrendezés.

    A rekurzív algoritmusok hasonlók az iteratívokhoz, de nem igaz rájuk, hogy újbóli végrehajtásukra csak akkor kerülhet sor amikor már az előző algoritmikus műveletsor végrehajtása lezárásra került, ill. ezzel összefüggésben az sem, hogy az újbóli futási menet bemenetét szigorúan az előző futási menet kimenete képezné. Sőt, egy rekurzív algoritmus önmaga ismételt végrehajtását tipikusan az algoritmikus műveletsor közepén igényli, ráadásul egyetlen futási meneten belül akár többször. Ebből adódóan a rekurzív algoritmusok sajátossága, hogy az egyes futási menetek belső állapotainak nyilvántartását ill. megőrzését igényli az ismételt végrehajtások idejére. Tipikus rekurzív (ill. rekurzióval effektívebben megoldható) algoritmus a permutációgenerálás, a fabejárás és a nyolc királynő probléma.

    Tehát elméletileg iteratív az az algoritmus ami verem nélkül, pusztán egy ciklusszerkezet segítségével megvalósítható, és rekurzív az, amire ez nem igaz, mert verem vagy más olyan módszer szükségeltetik a működtetéséhez, amely gondoskodik a futási menetek adatainak szeparált kezeléséről (pl. minden futási menet új objektumot hoz létre, ami köztes változóit az előző menetektől függetlenül, külön tárolja a végrehajtás idejéig).

    A gyakorlatban ugyanakkor az iteratív és rekurzív algoritmusok nem választhatók ennyire élesen szét, hiszen egy iteratív algoritmus is lekódolható rekurzív módon, ill. egy verem emulálásával egy tömbön a rekurzív algoritmus is átalakítható úgy, hogy valójában csak egy ciklusszerkezet legyen szükséges a működéséhez (kvázi iteratív legyen). Ezért inkább gyakorlatban azt szokás iteratív algoritmusnak hívni, amely nem tartalmaz önmagára hivatkozó eljáráshívást, és ezzel összefüggésben rekurzívnak pedig azt, amelyikre ez nem igaz, tehát amelyek az eljáráson, függvényen belül egy vagy több ponton saját magát hívja meg.
    Mutasd a teljes hozzászólást!
  • Üdv
    Ügyebár a rekurzív algoritmus az amelyik meghívja önmagát... de mi a hivatalos fogalmuk?
    Mutasd a teljes hozzászólást!
abcd