Rekurzív „alapfeladatok”

Egy kis „szó-magyarázkodás”

A rekurzió (latinul: recurso (1) visszafut, visszatér) „egy olyan művelet, mely végrehajtáskor a saját maga által definiált műveletet, vagy műveletsort hajtja végre, ezáltal önmagát ismétli; a rekurzió ezáltal egy adott absztrakt objektum sokszorozása önhasonló módon.” [Wikipedia]

Emlékeztető

A rekurzió leggyakrabban a függvényeknél fordul elő, mivel általa roppant tömören lehet a fogalmat definiálni. Találkozhattunk már vele a sorozatszámítás tételnél, az n-áris függvény binárisra visszavezetésénél. Így definiáltuk az ott szereplő F függvényt:

  F:H*→H
  F(x1,...,xn):=f(F(x1,...,xn-1),xn)  , ha n>0
  F():=F0                            , egyébként

Látszik a definíción, hogy

1. az első sora a függvény ún. szignatúrája (azt adja meg, hogy honnan hova képez);
2. van egy rekurzív ága, ahol saját magát felhasználja a számításhoz;
3. ezen az ágon a hívás paramétereinek száma (a sorozat hossza) csökken, ami által halad a 0 felé;
4. és van egy rekurziót nem tartalmazó ága (az n=0-hoz tartozó); ebbe „torkollik” minden számítás.

Gyakran fordul elő, hogy a paraméterlistán nem is jelenik meg minden adat, amivel dolgozik a függvény, csak a számítás előrehaladását jelző méret-paraméter. A fenti F függvény így is írható:

  F:N→H
  F(n):=f(F(n-1),xn)  , ha n>0
  F(0):=F0            , egyébként

Ebben az esetben –természetesen– feltesszük, hogy minden szükséges adat valamilyen módon elérhető a függvény számára. Amikor majd algoritmizáljuk (kódoljuk), akkor ezek a paraméterlistán meg nem jelenő adatok globálisan lesznek deklarálva.

Rekurzív specifikáció

A feladatokat gyakorta rekurzívan a legegyszerűbb specifikálni. Ilyenkor a következő visszatérő szerkezete van a specifikációnak:

  Be : N∈N, …
  Ki : S∈H
  Ef : N≥0 …
  Uf : S=F(N,…)
  Def:
     F:N×…→H
     F(n,…):=f1(F(ι1(n),…),…)  , ha T1(n,…) [1. rekurzív ág]
     …
     F(n,…):=fr(F(ιr(n),…),…)  , ha Tr(n,…) [r. rekurzív ág]
     F(n,…):=g1(n,…)           , ha U1(n,…) [1. nem rekurzív ág]
     …
     F(n,…):=gq(n,…)           , ha Uq(n,…) [q. nem rekurzív ág]
     
     ahol r,q>0 és
          ∀i∈[1..r]: fi:H×…→H  [H-értékű függvények] és
          ∀i∈[1..r]: ιi:N→N    [index-transzformációs függvények] és
          ∀j∈[1..q]: gi:N×…→H  [H-értékű függvények] és
          ∀i∈[1..r], ∀j∈[1..q]: Ti,Uj:N×…→L  [logikai függvények] és
          ∨(i=1..r)Ti ∨ ∨(j=1..q)Uj ≡ ↑     [teljes esemény-rendszert alkotnak]

Meggondolni valók

1. Mi lehet a szerepe a ι_j függvényeknek?
2. Az összegzés tételnél mik az egyes függvények?
   F :=    
   f_j:=    
   g_j:=    
   ι_j:=    
   T_j:=    
   

Rekurzív algoritmus

A fenti specifikációban „érdemi” rész összesen a definícióval kapcsolatos rész. Azt kell átírni algoritmikus nyelvre. Ez roppant mechanikus:

  Függvény F(Konstans n:Egész,…):TH
     Elágazás
       T1(n,…) esetén F:=f1(F(ι1(n),…),…)  [1. rekurzív ág]
       …
       Tr(n,…) esetén F:=fr(F(ιr(n),…),…)  [r. rekurzív ág]
       U1(n,…) esetén F:=g1(n,…)           [1. nem rekurzív ág]
       …
       Uq(n,…) esetén F:=gq(n,…)           [q. nem rekurzív ág]
     Elágazás vége
  Függvény vége.

Ha persze p=1, q=1, akkor nyilvánvalóan U=¬T (a teljes esemény-rendszer elvárás miatt). Ekkor egyszerűen:

  Függvény F(Konstans n:Egész,…):TH
     Ha T(n,…) akkor  F:=f(F(ι1(n),…),…)  [rekurzív ág]
             különben F:=g1(n,……)         [nem rekurzív ág]
  Függvény vége.  

Rekurzív Pascal kód

Semmi rendkívüli.

Az alábbiakban a függvények definícióját adjuk meg. Feladat: az algoritmusuk „legenerálása”.

Faktoriális

  Fakt(n):=1            , ha n=0
  Fakt(n):=Fakt(n-1)*n  , egyébként

Fibonacci

  Fibo(n):=n                    , ha n=0 ∨ n=1
  Fibo(n):=Fibo(n-1)+Fibo(n-2)  , egyébként

Binomiális együtthatók

Két rekurzív definíció is adható erre. Az egyik a Pascal-háromszögre épít, a másik pedig az „N alatt a K”-ára.

Binomiális együtthatók – Pascal-háromszög alapján

       0    1    2    3          …           n      ←k  
   0:  1 
   1:  1   1 
   2:  1   2   1 
   3:  1   3   3   1 
   …:  …                     
   n:  1   n   …                  n  1 

  BinomP(n,k):=1                              , ha n=0 ∨ k=0 ∨ n=k
  BinomP(n,k):=BinomP(n-1,k-1)+BinomP(n-1,k)  , egyébként

Binomiális együtthatók – „N alatt a K” alapján

Először is találjunk kapcsolatot a K. binomiális együttható és a K-1. között. Jelöljük –jobb híján– N_alatt_a_K-val az „N alatt a K”-t kiszámoló függvényt. Keressük azt a c∈N konstanst, amelyre teljesül: N_alatt_a_K(n,k)=c*N_alatt_a_K(n,k-1)! Azonos átalakítások után ezt kapjuk: c=(n-k+1)/k. Így a következő rekurzív összefüggés adódik:

  BinomS(n,k):=1                            , ha k=0
  BinomS(n,k):=(n-k+1)*BinomS(n,k-1) Div k  , egyébként

A függvény nevében az „S” arra utal, hogy a Pascal-háromszög egyetlen sorában lévő elemeket használjuk föl csupán a számításra.

Hanoi tornyai

A jól ismert feladat: át kell pakolni a „Hanoi torony” korongjait a baloldali pálcikáról, a jobb oldalira, miközben a középsőt is felhasználjuk. Feltétel: 1) a korongokat egyenként pakolgatjuk, és 2) mindig kisebbet rakunk nagyobbra.

A program adja meg a korongok mozgatásának utasításait, lépésről lépésre! Az algoritmizálásához egy ábrasorral szeretnék segíteni: töltse le vagy játssza le!! Próbálja ez alapján megalkotni a függvény-definíciót! A függvény fejsora legyen ez:

  Def:
    Hanoi:N×Ról×Val×Ra→Utasítás*
    
    ahol
      Ról,Val,Ra=Pálcika, Pálcika=(Bal,Közép,Jobb)
      Utasítás={BalrólKözépre,BalrólJobbra,
                KözéprőlJobbra,KözépzőlBalra,
                JobbrólKözépre,JobbrólBalra)

A függvény szignatúrájának magyarázatául:

1. 3 pálcika van (Bal,Közép,Jobb) – ez egy általunk definiált halmaz, amelynek majd egy felsorolás típust feleltetünk meg.
2. A függvény 3 pálcika paramétere jelzi, hogy meghívásakor mi az elérendő cél: N darab korong mozgatandó át Ról→Ra, és közben a Val pálcika is felhasználható.
3. Az Utasítás halmaz azokat a „mozdulatokat” tartalmazza, amelyeket egyáltalán egy koronggal el lehet végezni.
4. Az Utasítás halmaz iteráltja utal arra, hogy az eredmény utasítások sorozata lesz.

  Hanoi:N×Ról×Val×Ra→Utasítás*
  Hanoi(n,ról,val,ra):=IránybólUtasítás(ról,ra)    , ha n=1
  Hanoi(n,ról,val,ra):=Hanoi(n-1,ról,ra,val) & 
                       IránybólUtasítás(ról,ra) &
                       Hanoi(n-1,val,ról,ra)       , egyébként
  
  ahol
    IránybólUtasítás:Pálcika×Pálcika→Utasítás
    IránybólUtasítás(p,q):=... az Utasítás halmaz a paramétereknek 
                               megfelelő elemét választja ki ...
    pl. p=Bal, q=Jobb esetén BalrólJobbra-t.

A definíciót algoritmizálja!

  Függvény Hanoi(Konstans n:Egész, ról,val,ra:TPálcika):Szöveg
    Ha n=1 akkor
      Hanoi:=SPálcika(ról)+'->'+SPálcika(ra)+'|'
    különben
      Hanoi:=Hanoi(n-1,ról,ra,val) & 
             SPálcika(ról)+'->'+SPálcika(ra)+'|' & 
             Hanoi(n-1,val,ról,ra)
    Elágazás vége
  Függvény vége.

A kódoláson túli érdekessége a programnak, hogy információt szeretnénk kapni az algoritmusok bizonyos hatékonysági jellemzőiről: a rekurzív hívások számáról, a rekurzív hívások során használt verem
  A függvények hívásakor a paraméterek és az esetleges lokális változóik egy ún. verem adatszerkezetbe kerülnek.
  A függvényből való visszalépéskor a verem tetejéről törlődnek az utoljára betett értékek.
maximális mélységéről.

Gondolja meg: a függvények mely pontján és mit kellene tennünk, hogy a fenti kérdésekre választ kaphassunk! Annyi bizonyos, hogy deklarálnunk kell, globálisan
  (Miért is globálisan? Miért nem helyezhetők el az egyes függvényekben lokálisan?)
három változót, amelyeket az egyes függvények kezelni fognak: hívásSzám, aktMélység, maxMélység.

Tehát, hová és mi a teendő?
  A függvénybe belépéskor növelendő a hívásSzám és az aktMélység.
  Ekkor kell érzékelnünk, hogy a pillanatnyi veremmélység nagyobb-e, mint az eddigi maxMélység, mert ekkor ezt adminisztrálnunk kell.
  Kilépéskor az aktMélység csökkentendő.

Kódolja az algoritmusokat! Illessze be minden függvénybe a fenti globális változók beállítását, és persze gondoskodjon arról, hogy minden hívás előtt jó kezdő értéke legyen ezeknek.

A Hanoi torony kolásához: javaslom, hogy térjen el az algoritmustól abban, hogy nem szöveg függvényként valósítja meg. Ehelyett legyen eljárás belőle, és amikor a függvény a kimeneti értékét bővítette az algoritmusban, ott közvetetlenül írja ki. Azaz pl. az algoritmusban szereplő
 Hanoi:=SPálcika(ról)+'->'+SPálcika(ra)+'|'
értékadás „gyanánt” a Pascal kódban a
 Writeln(SPalcika(ról)+'->'+SPalcika(ra)+'|');
kiírás legyen!
Mindehhez kiindulhat a keretprogramból.

1. Készítse el a következő két függvénynek a definícióját!
1. Str2Int:S→N
   Pl. Str2Int('0123')=123
2. Int2Str:N→S
   Pl. Int2Str(0123)='123'
2. Vegye észre, hogy a Hanoi tornyai feladatban kapott összefüggés a korongok száma és a hívásszám között izgatóan „szabályos”. Fogalmazza meg a vélt szabályt, és próbálja meg matematikai módszerrel belátni!
   A többi esetében is létezik valamilyen szabályszerűség. A Fibonacci függvény esetében azonban némi érdekésséggel is bír. Gondolja ezt is meg!