Rekurzió a számítástechnikában

A rekurzió, mint az ismétlés eszköze

Ahogyan a rekurzív matematikai definíció az általa definiált fogalomra hivatkozik, úgy a rekurzív alprogram is tartalmaz hivatkozást saját magára. Ez az önmagára való hivatkozás biztosítja az ismételt végrehajtást. (Már ez alapján is lehet sejteni, hogy a rekurzív algoritmusok iterációval is megfogalmazhatók.) Az ismételt végrehajtások sorozatának is be kell fejeződniük véges időn belül. Ezt biztosítja a báziskritérium. Ez egy olyan feltétel, amely alapján eldönthető, hogy szükséges-e még további rekurzív hívás. Teljesülnie kell még továbbá annak is, hogy a rekurzív lépések sorozatával egyre közelebb kerüljön az algoritmus a báziskritériumhoz.
Fogalmak

A rekurzió

A rekurzív megfogalmazás (akár matematikai definíció, akár algoritmus) sok esetben ismétlésen alapuló eljárások tömörebb megadását teszik lehetővé.

A rekurzív algoritmus felépítése

Ahogyan a rekurzív matematikai definíció az általa definiált fogalomra hivatkozik, úgy a rekurzív alprogram is tartalmaz hivatkozást saját magára. Ez az önmagára való hivatkozás biztosítja az ismételt végrehajtást. (Már ez alapján is lehet sejteni, hogy a rekurzív algoritmusok iterációval is megfogalmazhatók.) Az ismételt végrehajtások sorozatának is be kell fejeződniük véges időn belül. Ezt biztosítja a báziskritérium, amely olyan feltétel, amely alapján eldönthető, hogy szükséges-e még további rekurzív hívás. Teljesülnie kell még továbbá annak is, hogy a rekurzív lépések sorozatával egyre közelebb kerüljön az algoritmus a báziskritériumhoz.

Rekurzív grafikai algoritmusok

Egyszerű rekurzív ábrákat előállító algoritmusok megértése segíti a rekurzív algoritmusok előállításához szükséges gondolkodásmód kialakulását. Valóban képszerűvé válnak a rekurzióval kapcsolatos fogalmak: báziskritérium, többszörös rekurzió, stb.
Fogalom

Koch-görbe

A Koch-görbe rajzolása:

• rajzoljunk egység hosszúságú szakaszt!
• a szakasz középső harmadát helyettesítsük a középső harmad, mint alap fölé rajzolt szabályos háromszög oldalaival!
• az előző lépést ismételjük meg a töröttvonal minden szakaszával a kívánt mélységig!

Megjegyzés: az egység hosszúságú szakaszból így nyert töröttvonal hossza az első lépés után 1 lesz. Ha tovább folytatjuk a műveletet, a töröttvonal hossza tovább nő szakaszonként 1/3-ad
résszel, azaz a töröttvonal hossza egyre hosszabb lesz a következő lépésben.

Koch-görbe

Fogalom

Sierpinski-háromszög

Sierpinski-háromszög rajzolása:

• Legyen adott három pont! Ezek lesznek a háromszög csúcspontjai.
• Rajzoljuk meg a háromszöget!
• Határozzuk meg mindhárom oldalának a felezési pontjait!
• Értelmezzük az előző két lépést arra a három háromszögre, melyeknek egyik csúcsa a háromszög egyik csúcsa, a másik kettő pedig a két szomszédos oldal felezési pontja.

Megjegyzés: cseréljük ki a „Rajzoljuk meg a háromszöget!” lépést a „Rajzoljuk meg a háromszög egyik csúcspontját!” utasításra.

Sierpinski-háromszög

Számítógéppel előállított rekurzív ábrák és természetes képződmények

A számítógépes technológia fejlődésével lehetővé vált, különböző természetes képződmények ábrázolása (a matematikai leírásuk alapján) és megjelenítésük. Ezek egyik népszerű alkalmazási területe a számítógépes játékok fejlesztése.
Fogalmak

Rekurzív algoritmusok csoportosítása

A rekurzió lehet egyszeres vagy többszörös aszerint, hogy a rekurzió adott szintjén egy vagy több rekurzív hívás történik.
A rekurzív hivatkozás lehet közvetlen vagy közvetett, aszerint, hogy a rekurzív algoritmus közvetlenül önmagára hivatkozik vagy egy másik alprogramra, amely hivatkozik rá.

Rekurzív adatszerkezet

Meg kell említenünk, mint rekurzív adatszerkezetet, a fát is. Felépítéséből adódóan a vele végzendő műveletek jelentős részét rekurzív módon célszerű megfogalmazni.

Számítógéppel előállított rekurzív ábrák és természetes képződmények

A fa-adatszerkezet

Programozási nyelvek és a rekurzió

A programozási nyelvek különböző megvalósításai, akár verziótól függően is támogathatják vagy sem a rekurzív programok írását.

Programozás:

Rekurzív az az eljárás vagy függvény, amely közvetve vagy közvetlenül önmagára hivatkozik. Rekurzív módon megadott függvénnyel a matematikában is találkozhatunk. Példa a faktoriális függvénye:
n! (olvasd: n faktoriális):=2·3·...·(n-1)·n, valamint 0!:=1
Ez a definíció rekurzív formára is átírható:
Így tehát az 5!-t visszavezetjük 5·4!-ra, vagyis 4!-ra, azt 3!-ra stb..., míg végül elérkezünk 0!-hoz, amit már nem vezetünk vissza. A legtöbb rekurzív utasítás tartalmaz egy leállási feltételt, ez akadályozza meg a végtelen rekurziót. A fenti függvény megvalósítása Pascalban:
Function Fakt(n:integer):integer;
 Begin
  if n=0 then Fakt:=1
         else Fakt:=n*Fakt(n-1); {a rekurzív hívás}
 End;
Látható, hogy a matematikai definíció szinte egy az egyben átírható volt Pascalra. Ennek az az oka, hogy a Pascal eljáráskezelése fel van készülve a rekurzióra: eljáráshíváskor a Pascal elmenti a verembe a globális, hívott eljárásban is szereplõ változókat, majd az eljárás lefutása után az eljárás lokális változói megszûnnek, és a verembõl elõkerülnek a globális változók. Ha végigkövetjük a függvény mûködését, kiderül, hogy voltaképpen az n·(n- 1)·...·2·1·1 szorzást végzi el, amit akár ciklussal is megoldhattunk volna. A ciklus elõnye a rekurzív megoldáshoz képest, hogy a veremigénye (és olykor az idõigénye is) kisebb. A rekurzív megoldások viszont sokszor érthetõbbek és áttekinthetõbbek.
1. feladat: vezesd vissza a hatványozást szorzásra a következõ definíció segítségével (írd meg a függvényt Pascalban):
Vagyis aⁿ=a·a^n-1, és a⁰=1, másképpen:
2. feladat: vezesd vissza a szorzást összeadásra! a·n=a+a·(n-1), és a·0=0.
3. feladat: vezesd vissza az összeadást eggyel való megnövelésre! Az Osszeg függvényben ne használd a + jelet, csak a Succ függvényt (eggyel való megnövelés)!
*** Matematikai kiegészítés (rekurzív függvények)
4. feladat: a Fibonacci-sorozat rekurzív definíciója: a₁=1, a₂=1, a_n=a_n-1+a_n-2 (n>2). Írd meg a Fib(n) függvényt rekurzív és nem rekurzív (ciklusos) módon is!
Vannak olyan feladatok, melyek mindenképpen rekurzív megoldás után kiáltanak, ciklussal való megoldásuk nagyon nehézkes. Ilyen a „Hanoi tornyai" néven ismert fejtörõ is. Adott három rúd, az elsõn n számú különbözõ méretû korong, csökkenõ sorrendben. A feladat átpakolni a korongokat a harmadik rúdra úgy, hogy egyszerre csak egy korongot mozdíthatunk, és nagyobb korongra rakhatunk csak kisebbet.
5. feladat: oldd meg a fenti fejtörõt 2,3,4 korongra!
Észrevehetõ, hogy pl. a háromkorongos feladathoz elõször a felsõ két korongot kell átpakolni valahogy a középsõ rúdra, majd az alsót a harmadikra, végül megint a felsõ kettõt, a középsõrõl a harmadikra. Így visszavezettük a feladatot egy kétkorongos feladatra és egy egykorongos feladatra. Ebbõl már látszik a rekurzív megoldás lehetõsége. Az eljárás Pascalban:
Procedure Hanoi(n,a,b,c:integer);
 Begin
  if n>0 then begin
     Hanoi(n-1,a,c,b);
     Writeln(n,'. korongot ',a,'. rúdról ',c,'. rúdra!');
     Hanoi(n-1,b,a,c);
  end;
 End;
n jelöli a korongok számát, a azt a rudat, ahonnan ennyi korongot át kell rakni, c a cél-rudat, b pedig a középsõt. n korongból a legalsót a program természetesen nem rakja át, csak kiírja, melyik rúdról melyik rúdra kell áttenni. a, b, c változók tartalmazhatják a rudak sorszámát. Az eljárás a fõprogramból indítható pl. Hanoi(5,1,2,3) módon az 5-korongos feladat megoldásához.
6. feladat: bizonyítsd be, hogy n rudas feladat 2ⁿ-1 lépésben oldható meg!
Rekurzív eljárásoknál látható, hogy a fordító, mire elérkezik a rekurzív híváshoz, már felismeri az eljárás azonosítóját. Ez közvetett rekurziónál Pascalban így nem mûködik:
Procedure Egyik;
 Begin
  Masik;
 End;
Procedure Masik;
 Begin
  Egyik;
 End;
Itt a fordító az Egyik eljárás fordítása közben nem ismeri fel a Masik azonosítót, mivel akkor még nincs deklarálva. Ekkor használható a Pascal forward direktívája, a következõképpen: az Egyik eljárás deklarálása elõtt meg kell adnunk a Masik eljárás fejlécét
Procedure Masik; forward;
módon. Ekkor az Egyik eljárás fordításakor a fordító már fel fogja ismerni a Masik azonosítót, noha a Masik eljárás fordítása csak késõbb történik. Forward használata esetén az eljárás fejlécét elsõ alkalommal teljes részletességgel (paraméterlistával együtt) kell megadni.