Rekurzia

V programovacom jazyku Pascal je možné vyvolávať procedúry a funkcie rekurzívne. Pod rekurzívnym vyvolaním rozumieme také vyvolanie, ktoré nastáva skôr, než bolo predchádzajúce vyvolanie ukončené.

Procedúry a funkcie, ktoré obsahujú rekurzívne vyvolanie, sa nazývajú rekurzívne. Rozlíšujeme pritom dva druhy rekurzie, a to

· rekurzia priama – ktorá nastáva u tej procedúry alebo funkcie, ktorá má vo svojom tele príkaz vyvolania samej seba (u procedúry) alebo zápis samej seba (u funkcie). K rekurzívnemu vyvolaniu prichádza tak, že procedúra alebo funkcia vyvolá samu seba.

· rekurzia nepriama (vzájomná), ktorá nastáva vtedy, keď dochádza k vzájomnému vyvolávaniu sa procedúr alebo funkcií. Prvá procedúra vyvolá druhú, druhá tretiu, atď, (n-1)–vá vyvolá n–tú a n–tá vyvolá prvú.

Príklad: Hanojské veže

Tento klasický matematický problém môže byť sformulovaný nasledovne:

Máme k dispozícii tri ihly a určitý počet diskov s rôznym priemerom a s otvorom uprostred. Na začiatku sú všetky disky napichnuté na jednej z ihiel tak, že tvoria vežu, smerom nahor sa zúžujúcu . Je potrebné premiestniť všetky disky na druhú ihlu pomocou tretej ihly, pričom musia byť dodržané nasledujúce pravidlá:

· v každom kroku je možné premiestniť len jeden disk z ihly na ihlu (disky nemôžu byť odložené vedľa ihly),

· nie je možné položiť väčší disk na menší.

Riešenie:

Na konkrétnom príklade najprv ukážeme postup pri riešení.

Predpokladajme, že počet diskov je rovný 3. Pomocou zápisu i –> j vyjadríme, že disk je presúvaný z ihly i na ihlu j . Celý postup pri troch diskoch je vyjadriteľný takto:

1 -->2

1 -->3

2 -->3 {Na treťom disku je veža tvorená 2 diskami}

1 -->2 {Posledný disk sa dostáva na svoju pozíciu}

3 -->1

3 -->2

1 -->2 {Všetky tri disky sú na druhom disku a tvoria vežu}

Celý postup by mohol byť popísaný pomocou príkazov

1. PRENES_DISK z ihly i na ihlu j

2. PRENES_VEZU (n, i, j, k)

ktorý interpretujeme takto: prenes n diskov z ihly i na ihlu j použitím ihly k.

V prípade, že n>0, je možné tento príkaz vyjadriť pomocou troch jednoduchších príkazov, a to

PRENES_VEZU (n-1, i, k, j) ,

PRENES_DISK (i, j) ,

PRENES_VEZU (n-1, k, j, i) .

V prípade, že n=0, niet čo prenášať.

Uvedený rozklad predstavuje rekurzívnu definíciu algoritmu riešenia a na jeho základe je možné vytvoriť rekurzívnu procedúru PRENES_VEZU. Procedúra PRENES_DISK bude vnorená v procedúre PRENES_VEZU a bude vypisovať príslušný prenos.

program HANOJ;

var pocet_diskov: integer;

procedure PRENES_VEZU (vyska, odkial, kam, pomocou: integer);

procedure} PRENES_DISK(odk, kam: integer);

begin

writeln(odk:3,'\Longrightarrow ',kam:3)

end; {PRENES_DISK}

begin {PRENES_VEZU}

if vyska>0 then

begin

PRENES_VEZU(vyska-1, odkial, pomocou, kam);

PRENES_DISK(odkial, kam);

PRENES_VEZU(vyska-1, pomocou, kam, odkial)

end

end; {PRENES_VEZU}

begin {Hlavný program HANOJ}

writeln('Zadajte, prosim, pocet diskov');

read(pocet_diskov);

PRENES_VEZU(pocet_diskov, 1, 2, 3)

end.

Podobne ako procedúry je možné vytvárať aj rekurzívne funkcie. Pomocou nich je možné naprogramovať mnoho matematických funkcií, ktorých definície majú rekurzívny charakter.

Jednoduchým príkladom je, napríklad, známa funkcia faktoriál, ktorá je definovaná takto:

Z tejto definície priamo možno napísať rekurzívnu funkciu

function FACT (N: integer): integer;

begin

if N<=0 then FACT:=1 else FACT:= N*FACT(N-1)

end}; {FACT}

Iným typickým príkladom je najväčší spoločný deliteľ dvoch kladných celých čísel

-- stručne NSD. Z vlastností NSD vieme, že platí:

ak A=B, tak NSD(A,B)=A=B,

ak A>B, tak NSD(A,B)= NSD(A-B,B),

ak B>A, tak NSD(A,B)= NSD(A,B-A).

Toto je rekurzívna definícia, ktorá môže byť zapísaná v tvare rekurzívnej funkcie nasledujúcim spôsobom:

function NSD(A, B: integer): integer;

{Vypočíta najväčší spoločný deliteľ dvoch celých kladných čísel}

begin

IF A = B THEN NSD:= A ELSE

IF A>B THEN NSD:= NSD(A-B,B) ELSE NSD:= NSD(A,B-A)

end; {NSD}

Rekurzívne definície sú obyčajne veľmi dobré popísané a sú založené na jednoduchých ideách.

Pri ich prepisovaní do pascalovskej procedúry alebo funkcie je potrebné dodržiavať nasledujúce zásady, aby sme sa vyhli chybám:

· Príkazová časť rekurzívnej procedúry (funkcie) musí obsahovať vetvu pre triviálny prípad niektorého základného parametra alebo vstupnej hodnoty. Táto vetva nebude obsahovať (rekurzívne) volanie procedúry (funkcie), ktorú práve definujeme.

· Ľubovoľné volanie procedúry (funkcie) vo vnútri jej príkazovej časti musí mať vhodne redukovaný argument (alebo globálnu hodnotu). Pri tejto redukcii sa očakáva, že raz dosiahne triviálny prípad po konečnom počte opakovaní.