Rekurzió

A Wikipédiából, a szabad enciklopédiából
Rekurzívan egymásba ágyazott ismétlődő kép.

A rekurzió a matematikában, valamint a számítógép-tudományban egy olyan művelet, mely végrehajtáskor a saját maga által definiált műveletet, vagy műveletsort hajtja végre, ezáltal önmagát ismétli; a rekurzió ezáltal egy adott absztrakt objektum sokszorozása önhasonló módon.

A nyelvtudományban a rekurzió alatt a tagmondatok egymásba ágyazását vagy azokat a szószerkezeteket értjük, amikor egy szó egy összetett szó része, így a rekurzió révén potenciálisan végtelen számú, különböző mondatot hozhatunk létre.

Rekurzió a matematikában[szerkesztés | forrásszöveg szerkesztése]

A rekurzió matematikai használatban gyakran előkerül függvényeknél, halmazoknál, és kifejezetten a végtelenül önhasonló fraktálok esetében.


Függvények rekurziójára kiváló példa a Fibonacci-sorozat, ahol a függvény részben önmaga egy változatát hívja meg: F(n) = F(n − 1) + F(n − 2). A Fibonacci-számok rekurzív definíciójánál azonban fontos kikötni két, a rekurzióból nem következő kitételt, miszerint F(0) = 0, valamint F(1) = 1.

Egyes definíciókat rendszerint rekurzív alakban adnak meg, így például a logikai formula fogalmát is rekurzívan definiálják. Kimondják, hogy a logikai változók és konstansok formulák, majd megadják az eszközöket, amikkel az egyszerűbb formulákból lépésenként bonyolultabb formulák építhetők fel. Ilyen eszközök például a logikai műveletek, kvantorok, zárójelek. Végül kimondják, hogy az így felépíthető formulákon kívül nincs más logikai formula.

Rekurzió a számítógép-programozásban[szerkesztés | forrásszöveg szerkesztése]

A rekurziót leggyakrabban a visszalépéses keresés (angolul backtracking) jellegű algoritmusokban szokták használni. A rekurzív algoritmusok ciklussá formálása "automatikusan" elvégezhető verem bevezetésével. Sőt! Minden magas szintű programozási nyelvben megírt rekurzió - pontosabban minden függvényhívás - végül hívási verem (angolul call stack) segítségével valósul meg.

A magas szintű forráskódban a ciklussá alakítás ugyanakkor nem feltétlenül éri meg, mert a kód veszíthet az átláthatóságából, tömörségéből. Mindez az alábbi példán is megfigyelhető.

Az egyik legszemléletesebb példa a rekurzióra a faktoriális számító függvény, melynek C nyelvű implementációja az alábbi:

int faktorialis(int n)
{
    if(n <= 1)
        return 1;
    return n * faktorialis(n-1);
}

A függvény tehát egy egész értékkel tér vissza, ami a bemeneti szintén egész számtól függ, mégpedig úgy, hogy a függvény számítás közben meghívja saját magát, de egyel kisebb bemeneti paraméterrel, mígnem n el nem éri az 1-et, és a számítás végetér. Természetesen ugyanez az eredmény elérhető egy iteráció segítségével is:

int faktorialis(int n)
{
    int eredmeny = 1;
    int i = 2;
    while(i <= n){
        eredmeny = eredmeny * i;
        i = i + 1;
    }
    return eredmeny;
}

Minden rekurzió triviálisan ciklussá alakítható (egy külön vezetett verem segítségével) és minden ciklus rekurzióvá alakítható. Egy algoritmus implementálásának a stílusát érthetőségi és hatékonysági szempontok alapján szokták megválasztani. Egy fa-szerű adatszerkezet mélységi bejárása megoldható iteratívan is, de rekurzióval leírva könnyebben követhető és még hatékony is.

Ahogyan ciklusok esetében előfordulhat véletlenül végtelen ciklus, úgy rekurziók esetében is lehetséges a végtelen rekurzió. Az előbbinek a tünete lehet a "befagyott program" az utóbbinak pedig az "elszállás". Ilyenkor általában elfogy a hívási verem (call stack) számára fenntartott memória és veremtúlcsordulási hibával (stack overflow error) megszakad a program.

Rekurzió a nyelvészetben[szerkesztés | forrásszöveg szerkesztése]

A rekurziónak fontos helye van az elméleti nyelvészetben, ahol a mondatok végtelen kombinálásának mechanizmusát vizsgálják. A téma meghatározó területe egyes orvos tudományi (betegségek esetén, mint például afázia) és pszichológiai kutatásoknak is.

A rekurzió végtelenített ismétlődő jelentése megjelenik a nyelvi - főképp szakmai - humorban is. Van olyan, hogy egy szakmai könyv indexében a rekurzió magyarázatára azt találjuk, hogy a választ „lásd: rekurziónál”. A Google keresőbe is beépítettek apró vicces változatot a témára. Ha beírjuk a keresőbe, hogy „rekurzió”, akkor a találatok felett megjelenik a „Keresési javaslat: rekurzió” (ál)alternatív javaslat, amire kattintva ugyanazt az oldal betöltési eredmény kapjuk vissza.

Források[szerkesztés | forrásszöveg szerkesztése]

Lásd még[szerkesztés | forrásszöveg szerkesztése]