Rekurzió
 |
Ehhez a szócikkhez további forrásmegjelölés szükséges az ellenőrizhetőség érdekében. Ez önmagában nem minősíti a tartalmát: az is lehet, hogy minden állítása igaz. Segíts a szócikk fejlesztésében további megbízható források hozzáadásával. |
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.
Tartalomjegyzék |
Rekurzió a matematikában[szerkesztés]
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]
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]
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ő angol változatba, hogy „recursion”, akkor a találatok felett megjelenik a „Did you mean: recursion” (ál)alternatív javaslat, amire kattintva ugyanazt az oldal betöltési eredmény kapjuk vissza.
Források[szerkesztés]
Lásd még[szerkesztés]
 |
Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |
