B. függelék: a rekurzió

Rekurzió az, amikor egy eljárás vagy függvény - közvetve vagy közvetlenül - önmagát hívja. Az ilyen eljárások és függvények rekurzívak. A végtelen rekurzió elkerülésére szükségünk van egy feltételre, amely valamilyen lépésszám után leállítja a rekurziót. A következõ eljárás ciklus helyett rekurziót alkalmaz adott számú * kiraj zolására.

Procedure Csillagok(mennyi:integer);
 Begin
    If mennyi>0 then begin
       write('*');
       Csillagok(mennyi-1);
    end;
 End;

Az elv: adott számú csillagot úgy rajzolunk, hogy kirajzolunk egy csillagot, majd kirajzoljuk a maradékot. mennyi paraméter azt jelzi, hogy hány csillagot kell még kirajzolni. A feladatot (sok csillag) így visszavezettük egy egyszerûbb feladatra (egy csillag).

A matematikában találkozhatunk rekurzív definíciókkal. Így pl. 0! (nulla faktoriális) értéke 1, n! pedig n·(n-1)!. Tehát egy szám faktoriálisát úgy számítjuk ki, hogy kiszámítjuk a nála eggyel kisebb szám faktoriálisát (egyszerûbb feladat!), és megszorozzuk a számmal. A rekurzió véget ér, ha eljutunk a 0-hoz.

Function Fakt(n:integer);
 Begin
    If n>0 then Fakt:=n*Fakt(n-1)
           else Fakt:=1;
 End;

A rekurzív eljárások igénybe veszik a stack-et. A második példában a függvény paramétere minden egyes függvényhíváskor eltárolásra kerül, s a hívott függvény saját változóként újból létrehozza. Mire sorozatos függvényhívásokkal eljutunk a 0-hoz, a veremben ott sorakoznak az eltárolt paraméterek:Fakt(5)-nél 5, 4, 3, 2, 1. Ebbõl is látszik, hogy memóriafoglalás, sõt, olykor sebesség szempontjából a rekurzió nem hatékony, viszont egyes feladatokat rekurzív szemlélettel nagyon könnyû megoldani (ne a programozó dolgozzon, hanem a gép!).

A közvetett rekurzió alábbi megvalósítása hibás:

Procedure Egyik(n:integer);
 Begin
    Masik(n-1);
 End;

Procedure Masik(n:integer);
 Begin
    If n>0 then begin
       writeln(n);
       Egyik(n-1);
    end;
 End;

Az Egyik eljárás fordításakor a Masik eljárás még nincs deklarálva, és ez fordítási hibához vezet. A megoldás a következõ. Az Egyik eljárás deklarálása elé be kell írni:

Procedure Masik(n:integer); forward;

A forward szó jelzi a fordítónak, hogy a megadott eljárás késõbb kerül deklarálásra, és itt csak az eljárás fejét kell megadni.

Rekurzív adatszerkezetek

A dinamikus memóriakezelésre és a Type deklaráció rekurzív használatára mutat példát a következõ program. Az itt megvalósított adatszerkezet neve lista. Minden eleme tartalmaz egy adatot (hiszen a lista feladata a tömbhöz hasonlóan adattárolás), és egy mutatót, amely megmutatja, hogy a következõ listaelem hol van a memóriában.

TYPE listamutato=^listaelem;
     listaelem=record
                adat:integer;
                mutato:listamutato;
               end;

A TYPE, mint látható, felismeri a közvetett rekurziót. A továbbiakban szükségünk van egy pointerre, amely megmutatja a lista elsõ elemének helyét a memóriában, és egy másikra, amely a lista aktuális elemére mutat.

VAR fej,p:listamutato;

A következõ példaprogram létrehoz egy háromelemû listát.

BEGIN
 New(fej);
 fej^.adat=567;

A memóriában létrejött egy rekord, melyre a fej pointer mutat. Maga a rekord elérhetõ mint fej^. A rekord .adat mezõje egy integer változó, a .mutato mezõje viszont egy pointer, mely a lista következõ elemére mutat (most még nem mutat sehová).

 New(fej^.mutato);

Itt hoztuk létre a lista második elemét, melyre fej^.mutato mutat. Hogy áttekinthetõbb legyen, bevezetjük a p mutatót ehelyett (bár használhatnánk akár a ((fej^.mutato)^.mutato)^.adat formát is).

 p:=fej^.mutato;
 p^.adat:=1288;
 New(p^.mutato);
 p:=p^.mutato;
 p^.adat:=17;
 p^.mutato:=NIL;
END.

Hogyan lehet felszabadítani a memóriát? Végig kell lépegetni a listán a fejétõl kezdve. Vigyázat, még a p által mutatott rekord megsemmisítése elõtt el kell tárolni, hová mutat a törlendõ listaelem!

p:=fej;
while p<>NIL do begin
   q:=p^.mutato;
   Dispose(p);
   p:=q;
end;

Természetesen a legelegánsabb a rekurzív megoldás, hívása: Felszabadit(fej)

Procedure Felszabadit(p:listamutato);
 Begin
    If p<>NIL then begin
       Felszabadit(p^.mutato);
       Dispose(p);
    End;
END;

(Ez az eljárás hátulról visszafelé szabadítja fel a listát, legutoljára a fejrekordot törli.)

Ha a fentieket megértetted, elmondhatod magadról, hogy konyítasz valamicskét a programozáshoz. Ha nem, ne szomorkodj: a B függelék csak a teljesség kedvéért került a füzetbe, és enélkül is ugyanolyan jó programokat írhatsz. Mert most már nincs más hátra: válassz egy feladatot, fogj neki, és írj rá programot! Sok sikert.