Rekurzió

Rekurzívan egymásba ágyazott ismétlődő kép

A rekurzió a matematikában, valamint a számítástudományban egy olyan művelet, amely végrehajtásakor 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

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-számok, 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

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. Ezen kívül 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álisszámító függvény, amelynek 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 eggyel 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++;
    }
    
    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 faszerű 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

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. Bár rekurzió révén potenciálisan végtelen számú mondat hozható létre, Fred Karlsson 2007-ben tizenhat nyelvre kiterjedő vizsgálatai szerint az írott nyelvben maximum háromszoros, a beszélt nyelvben maximum kétszeres beágyazás található.

A téma meghatározó területe egyes orvostudomá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 oldalbetöltési eredményt kapjuk vissza.

Források

• Hunyadi László (szerkesztő): Rekurzió a nyelvben I. Prozódiai megközelítés, Tinta Könyvkiadó, Budapest, 2011
• Bánréti Zoltán (szerkesztő): Rekurzió a nyelvben II. Neurolingvisztikai megközelítés, Tinta Könyvkiadó, Budapest, 2011
• Csépe Valéria, Honbolygó Ferenc (szerkesztő): Rekurzió a nyelvben III. Pszichológiai és idegtudományi megközelítés, Tinta Könyvkiadó, Budapest, 2011
• Kornai, András (2010. Aug). „Rekurzívak-e a természetes nyelvek?”. Magyar Tudomány. (Hozzáférés: 2024. július 1.) 

Kapcsolódó szócikkek

• rekurzív sorozat
• ciklus (programozás)
• Vezérszó