Rekurzió pascalban

A rekurzió egy programozási módszer. Azt az esetet nevezzük így, amikor egy eljárásban szerepló kód önmagát (ugyanazt az eljárást) hívja meg.Természetesen a folyamatot ebben az esetben is véges számú lépés után meg kell állítani.



Talán a legegyszerűbb példa a faktoriális értékének kiszámítására szolgáló programkód:

 Egy szám faktoriálisának kiszámításának algoritmusa:

 Ha n = 0 akkor
   fakt =1                  //hiszen 0! = 1
 Egyébként
   fakt = fakt(n-1)*n
 Elágazás vége

 Nézzük meg Pascal nyelven hogyan néz ki a rekurzív függvény:

20. Function Faktorialis(n:Integer):LongInt;

21. Begin

22.   If n = 0 Then Faktorialis:=1

23.   Else Faktorialis:=Faktorialis(n-1)*n;

24. End;

A rekurzió használata lehetővé teszi programok (az algoritmusok) leegyszerűsítését és jobban átlátható kód készítését. A rekurzív függvényhívás erőforrás igényes művelet, hiszen minden esetben a függvény ismételt meghívásakor a paramétereknek és az adminisztrációs adatoknak (a rutin lokális változói, paraméterei, visszatérési cím) a veremben foglalja le a program a területet, vagyis a rekurzió mélységét (az egymásba ágyazások számát) a rendelkezésre álló verem mérete korlátozza.
Rekurzív eljárások, illetve függvények futásánál fennáll az a veszély, hogy a hívásokat semmi sem állítja le, hiszen az egymásból való hívások száma elvileg végtelen lehet. Gyakorlatilag azonban végtelen rekurziót nem könnyű előállítani, hiszen a rekurzió használja a vermet, és ha mást nem is, a visszatérési címet minden esetben oda teszi. Mivel a verem nagysága véges, az előbb-utóbb betelik. Ha a program figyelte a verem túlcsordúlását, akkor az futási hibával leáll (stack overflow) , egyéb esetben a memória további része drasztikusan felülíródik, aminek következtében a rendszer is elszállhat.
Minden rekurzív algoritmus átalakítható nem rekurzívvá, azaz létezik iteratív megoldása is. Az átalakítás első lépése, hogy a processzor saját verme helyett egy explicit vermet használunk az algoritmus állapotának tárolására: rekurzív hívás helyett egy új elemet tolunk a verembe, visszatérés helyett kiveszünk egy elemet a veremből, és kombináljuk az eddigi részeredményekkel. Az így kapott algoritmus már iteratív, de általában tovább javítható. Az iteratívvá alakított algoritmus általában kevesebb memóriát használ, mert a saját vermébe kevesebb információt helyez el, mint a processzor tenne a hívóverembe, viszont nehezebben követhető.

Mit nevezünk rekurzív feladatnak

Egy feladat rekurzív, ha a feladat megoldásához vezető lépések során

• találunk egy legegyszerűbb esetet, melyben a megoldás magától értetődik, és
• találunk egy olyan ismételt egyszerűsítési folyamatot, mely alapján véges lépésben eljuthatunk a legegyszerűbb esethez. Minden egyes lépésnél feltételezzük, hogy a következő, egyszerűbb esetnek már megvan a megoldása.

E módszer a teljes indukció elvén alapszik. A feladatot mindig visszavezetjük egy előző feladatra, melynek megoldása egy fokkal egyszerűbb. Véges lépésben elérjük a legegyszerűbb esetet, és így a feladatot megoldottuk.

Rekurzió típusai

Egy függvényt vagy eljárást rekurzívnak nevezünk, ha az meghívja saját magát. Két típusú rekurziót különböztetünk meg:

• Közvetlen rekurzió:a rutin közvetlenül saját magát hívja. Például A rutin hívja A rutint.
• Közvetett rekurzió:a rutin csak közvetve hívja meg saját magát egy másik rutin hívásán keresztül. Például:A hivja B-t, B hívja A-t.

Rekurzív rutin tartozékai

• Kell lennie valaminek, ami a hívások során változik (pl. egy paraméter,nevezzük n-nek), és elvileg elérhet egy küszöböt.
• Kell lennie egy olyan utasításnak, mely ezt a valamit (n) a küszöb felé viszi.
• Illetve kell egy leállító feltétel, amely arról a bizonyos valamiről (n) eldönti, elérte-e a küszöböt. Ha igen, akkor nem történik több rekurzív hívás.