III. A rekurzió

Elsõ nekifutás: a rekurzió fogalma

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.

Második nekifutás: rekurzív adatszerkezet-feldolgozás, listák

A rekurzív függvények egy jellegzetes fajtáját, a listakezelõ függvényeket a LOGO nyelv segítségével ismerjük meg. Most nem a nyelv rajzoló, hanem függvényszerû részével foglalkozunk, mely a LISP mesterséges intelligencia-nyelv listakezelését vette át.

Egy függvényszerû nyelvben minden eljárás függvény. Változók nincsenek, csak függvényparaméterek. A ciklusok szerepét a rekurzió veszi át. Példa LOGO függvény deklarálására:

TO Fakt :N
   IF :N = 0 [OP 1][OP Fakt :N - 1]
END

Egy sorban akárhány utasítás állhat. Kettõsponttal jelöljük a paramétereket. Az OP a visszaadott értéket jelenti. Az IF után két lista következik (szögletes zárójelben), az egyik az akkor-, a másik a különben-ág. Ezt hasonlítsd össze az azonos feladatú Pascal függvénnyel!

A lista felsorolás-jellegû adatszerkezet. A LOGO-ban a listát szögletes zárójel határolja. Pl.: az [1 [f f] 2 3 xxx] egy 5-elemû lista (második eleme maga is lista). Mivel a LOGO típus nélküli nyelv, egy listában elhelyezhetünk vegyesen számokat és szövegeket. (Másik fajta listája a LOGO-nak a karakterekbõl álló lista, a fenti lista 5. eleme az "xxx karakterlista, ennek elsõ eleme pedig az "x karakter.) A listában általában értelmezett mûvelet az eleje és maradék függvény. Elõbbi megadja a lista elsõ elemét, utóbbi az elsõ elemétõl megfosztott maradék listát. LOGO-ul:

FIRST :L és BUTFIRST :L (röviden BF)
(Továbbá felhasználjuk: EMPTY? :L - üres-e a lista -, PRINT kif. - kiírás.)

Így FIRST [1 2 3] értéke 1, míg BUTFIRST [1 2 3] értéke [2 3] maradék lista lesz.

Példa: adjuk meg lista utolsó elemét. Rekurzív szemlélettel: egyelemû lista utolsó eleme egyben az elsõ is, hosszabb lista utolsó eleme pedig megegyezik a maradék lista utolsó elemével. Mivel a maradék rövidebb, így visszavezettük a feladatot egyszerûbbre. (A feltétel úgy állapítja meg, hogy egyelemû-e a lista, hogy megnézi, a maradék üres-e).

Utolso :L
   IF EMPTY? BUTFIRST :L [OP FIRST :L][OP Utolso BUTFIRST :L]

1. feladat: Mit csinál a következõ függvény, és hogyan mûködik:

Valami :L
   IF NOT EMPTY? :L [PRINT FIRST :L Valami BF :L]

A fenti függvénynek nincs visszaadott értéke, viszont van mellékhatása (kiír valamit).

Példa: lista elemeinek megszámolása (a maradék lista elemszámánál eggyel több):

Elemszam :L
   IF EMPTY? :L [OP 0] [OP (Elemszam BF :L) + 1]

2. feladat: írd meg az Eleme :L :N függvényt, amely megadja az :L lista :N. elemét! Segítség: az elsõ eleme (ha :N=1) egyszerû FIRST, egyébként viszont a maradék listának kell venni az :N-1. elemét.

Lista összeállításához használható az FPUT :E :L függvény, melynek eredménye az :L lista, elejére téve az :E elemet. Ennek segítségével lista végére így tehetünk elemet (vagyis leválasztjuk a lista elsõ elemét, a maradéknak a végére tesszük az elemet, majd visszaragasztjuk az elsõ elemet):

Vegere :E :L
   IF EMPTY? :L [OP FPUT :E :L]~
                [OP FPUT (FIRST :L) (Vegere :E BF :L)]

(A ~ azt jelöli, hogy az utasítást egy sorba kell írni, csak a lapra nem fért ki.)

3. feladat: írd meg a Kivesz :E :L függvényt (eredménye az :L lista, kivéve az :E elemet). Két lehetõség van: vagy az :E elsõ elõfordulását veszed csak ki, vagy minden, :E-vel egyezõ elemet. Írd meg mindkét változatot! (Tipp: ha az elsõ elem az :E, a maradék listát kell venni...)

4. feladat: írd meg a Kidob :L :N függvényt (eredménye az :L lista, kivéve az :N. helyen álló elemét).

5. feladat: írd meg a Fordit :L függvényt (megfordítja a listát)! A korábban deklarált függvényeket felhasználhatod benne.

A rekurzív programok sebességében (és veremigényében) drasztikus romlást okoz, ha szükségtelenül sok függvényhívást használunk. Nézzük meg a Maxi függvényt, mely egy lista legnagyobb elemét választja ki a következõ elgondolás szerint:

- Egyelemû lista maximuma az elsõ eleme
- Egyébként lista maximuma az elsõ eleme és a maradék lista legnagyobb eleme közül a nagyobbik

Ez kódolva:

Maxi :L
   IF EMPTY? BF :L [OP FIRST :L]~
                   [IF Maxi BF :L > FIRST :L [OP Maxi BF :L]~
                                             [OP FIRST :L] ]

A függvény egy lépésben kétszer is meghívhatja magát (egyszer a feltétel, egyszer a végeredmény kiszámításánál, Maxi BF :L-lel), ezzel a lépések száma n helyett akár 2ⁿ is lehet, ahol n a lista hossza (minden lépés megkétszerezi az eljáráshívások számát). Az egyik megoldás egy változó használata lenne, amelyben eltároljuk a kiszámított értéket, és másodszor már az eltárolt értéket használjuk fel rekurzív hívás helyett. A LOGO nyelvben lehet változókat is létrehozni. Egy függvényszerû nyelvben azonban nincsen erre feltétlenül lehetõség. Ekkor használhatunk egy másik eljárást, melynek paraméterként adjuk át a kiszámított értéket.

Maxi :L
   IF EMPTY? BF :L [OP FIRST :L]~
                   [OP Nagyobb FIRST :L Maxi BF :L]

Nagyobb :A :B
   IF A>B [OP A][OP B]

Így még áttekinthetõbbé is vált a függvény.

6. feladat: írd meg a maximumkiválasztásásos rendezés rekurzív változatát (RENDEZ :L)! Segítség: egyelemû lista rendezett. Egyébként vedd ki a legnagyobb elemet, a maradék listát rendezd, majd ragaszd az elejére a kivett elemet.

7. feladat: még további feladatok listakezelésre:
   lista végére adott elemet ragaszt
   megadja a lista valahányadik elemét
   két listát összeilleszt

A rekurzió fontos és hasznos programozói fogás. Sok esetben pár sorban meg lehet oldani vele egyébként hosszú programot igénylõ feladatokat. További alkalmazását ld. pl. a rekurzív adatszerkezetek (2. Pascal füzetke B függeléke), a PROLOG nyelv, a Quicksort rendezés bemutatásánál.