Programozás módszertan

III. Félév - rekurzió

Mi is a rekurzió? Válasz: Önmagát újra meghívó eljárás. Matematikában már biztos sokan találkoztak rekurzív módon megadott algoritmusokkal. Ott az volt a lényeg hogy a sorozat előző tagjából lehetett ellő állítani a következő tagot. Ilyen híres sorozat például a Fibbonacci sorozat. Programozásban is valami hasonlót értünk alatta. A rekurziónál az eljárás vagy függvény saját magát hívja meg újra. Néha változnak a paraméterek, de ez nem feltétlenül igaz. Nézzünk meg először egy könnyed kis példát aztán majd boncolgatjuk előnyeit, hátrányait. Tehát a feladat az előbb említett Fibonacci sorozat rekurzív módón való előállítása:

Függvény fib (n: egész): egész
ha n=0 akkor fib:=0 
    különben 
    ha n=1 akkor fib:=1 
    különben fib:=fib(n-1)+fib(n-2) 
függvény vége 

Remélem ebből már lehet látni hogy működik a rekurzív algoritmus. Ha a feltételek nem teljesülnek meghívja magát újból az algoritmus, mindjárt kétszer. Nézzük mi fog végbemenni n=3 esetén:

N=3-nál n=0 nem teljesül megyünk különben ágra, n=1 sem teljesül úgyhogy meghívjuk a fib függvényt n=2-re ill. n=1-re.

N=2-nél fib újra meghívja n=1-et és n=0-t.Itt n=1-re egyet kapunk majd n=0-ra 0-t. Visszamegyünk n=3 szintre és folytatjuk ott ahol félbeszakadt az algoritmus n=1 ág is végrehajtódik. Ez egy. Az összeg így fib(2)+fib(1)=1+1=2. És tényleg 2 az összeg hisz a fib első 3 tagja: 1,1,2…

Az előző példa egy egyszerű alkalmazása a rekurziónak, de itt már lehet látni a gyengeségeit is. Hiszen n=3-nál is már kiszámoljuk fib(1)-et majd később n=2 ágnál újra kiszámoljuk. Ez egy fölösleges számolás. N=4-nél már sokkal több ehhez hasonló lépés lenne.

Ennek ellenére sok probléma megoldására hatékonyabb a rekurziót alkalmazni. Sok esetben nem hajtódnak végre fölösleges lépések, és ez pl. a rendezéseknél nagy előre lépést jelenthet majd.

Nézzünk meg most egy kicsit látványosabb példát, a Hanoi tornyokat.

Hanoi tornyok

Van 3 oszlopunk. Az egyiken vannak különbözőnagyságú gyűrűk. A gyűrűk nagyság szerint rendezve vannak, felfele csökkennek.

A feladat: a kupac átpakolása a másik oszlopra, úgy hogy egyszerre csak egyet rakhatunk át, és egy gyűrűt csak nála nagyobb gyűrűre lehet rakni.

A feladat megoldása egy legendához köthető: Valamelyik kolostorban a helyi szerzetes szintén ezt a feladatot kapta, méghozzá 100 gyűrűvel. A szerzetes kidolgozta a megoldást. A feladatot 3 részfeladatra bontotta le:

1, Tegyünk át 99-et a c oszlopra.

2, Tegyük át a maradék egyet a b oszlopra.

3, C oszlopról tegyük át 99-et a b oszlopra.

Ezután belátta, hogy a legegyszerűbb lépés a kettes. Úgyhogy ő megcsinálja azt, a többit majd kiosztja a tanítványai között.

Tehát a feladat megoldása így nézett ki.

I, Add ki feladatnak n-1 gyűrű átrakását a-ról c-re.

II, Tedd át a maradék 1 a-ról b-re.

III, Add ki feladatnak n-1 gyűrű átrakását c-ről b-re.

Lehet látni hogyha az I.-t megcsináljuk akkor már a III-as sem gond. Tehát kövessük a szerzetes megoldását és alkalmazzuk az 1. pontra. Pl. Ha 100 gyűrűnk van az egyes pont szerint 99 gyűrűt át kell rakni a-ról c-re. Hogyan rakjunk át 99-et a másik toronyra? A főszerzetes szerint így:

1, Add ki feladatnak n-1 gyűrű átrakását a-ról c-re.

2, Tedd át a maradék 1 a-ról b-re.

3, Add ki feladatnak n-1 gyűrű átrakását c-ről b-re.

Tehát csak át kell adni a feladatot valakinek, hogy 98-at rakjon át és akkor már menni is fog.

Innen már lehet látni hogy III. feladat teljesítése is hasonlóan megy. Tehát az algoritmus így néz ki:

eljárás hanoi(n: egész; a,b,c:karakter) //n a korongok száma
  ha n>0 akkor 
         hanoi(n-1,a,c,b)
          ki: a,b
         hanoi(n-1,c,b,a)
   elágazás vége
eljárás vége

Ez egy kicsit hosszabbra sikeredet mint gondoltam, remélem érthető a megoldás menete. Ez egy nem könnyű eljárás, de ha ezt érted akkor a rekurzióval már kevesebb gondod lesz. Egy hasonló eljárást fogunk most vizsgálni. A feladat n szám permutációinak kiíratása lesz.

Permutáció

Itt először is a főprogramban létrehozunk egy üres halmazt. Ebben fogjuk tárolni az eddig már fölhasznált elemeket. X tömbben pedig a sorozat elemeit. Az algoritmus lényege az hogy ciklikusan végigmegyünk az elemeken, és ha valami nincs benne a halmazban akkor azt belerakjuk, majd újra meghívjuk az algoritmust csak most kevesebb elemre, és a halmaz nem lesz üres. Na ez így egy kicsit bonyolult, tehát lássuk a gyakorlatban is mindezt:

Eljárás permutáció (n, i : egész; változó x: tömb; marvolt: halmaz) 
Változó c, j: egész

	Ha i>n akkor ki x 
		   Különben
			   ciklus j:=1-től n-ig 
			 	 Ha j eleme  marvolt akkor 
				        x[i]:=j
			           permutáció (n,i+1,x,marvolt + j)
			    elágazás vége
			ciklus vége
	elágazás vége
eljárás vége

Ugye itt is arról van szó, hogy lefut az algoritmus első körben n-ig majd viszont visszaugrik egy korábbi állapotba a program, méghozzá i=2 állapotba. De ekkor már túl van az ellenőrzésen, de a ciklus folytatódik és j tovább növekszik.

Quick sort

Ha ezt a példát meg az előzőt megértettük nem okozhat majd gondot a következő sem. Ez pedig a quick sort rendezés. Az eljárás lényege hogy vesszük a sorozat első elemét. Ez a szám elé tesszük az összes többi nála kisebb elemet. Ha ez megvolt akkor ahova bekerült ez az elem az elejétől eddig az elemig újra rendezzük, majd utána a végét rendezzük.

Eljárás quick (a: tömb; e, v: egész)
      Szétválogat (a, e, v, k)
      Ha k-e>1 akkor quick(a,e,k-1)
      Ha v-k>1 akkor quick(a, k+1, v)
Eljárás vége

A szétválogat eljárás a tömbben az elemeket szétválogatja az alapján hogy a[e]-nél kisebb e a többi elem.

Az összes program letölthető innen. Hamarosan bővülni fog a kínálat, pl. föl kerülnek majd a programozási tételek rekurzívan. A honlapon találhatóak egyéb programok is mint pl. a cégalap ami egyik gyak. órának volt anyaga, de az a backtrack-es feladatok közés sorolható inkább.

Ha valami nem világos írj e-mail-t, szívesen válaszolok rá.