REKURZIÓ. Rekurzív: önmagát ismétlő valami (tevékenység, adatszerkezet stb.) Rekurzív függvény: függvény, amely meghívja saját magát

Petrik tananyagtár: Rekurzió Petrik Lajos Vegyipari, Környezetvédelmi és Informatikai Szakközépiskola Szoftverfejlesztő szak, 14. évfolyam, OKJ szám: 54 481 02 0010 54 04

___________________________________________________________________________

REKURZIÓ 1. ˗ ˗ 1.1

A REKURZIÓ FOGALMA Rekurzív: önmagát ismétlő „valami” (tevékenység, adatszerkezet stb.) Rekurzív függvény: függvény, amely meghívja saját magát. Bevezető példák:

1.1.1 Faktoriális Nemrekurzív specifikáció: n! = 1 * 2 * 3 *… * n ha n > 0 1 ha n = 0 Rekurzív specifikáció: n! = n * (n – 1)! ha n > 0 1 ha n = 0 Rekurzív algoritmus: Függvény Faktoriális(n: egész): egész Ha n > 0 akkor Faktoriális := n * Faktoriális(n – 1) különben Faktoriális := 1 Elágazás vége Függvény vége

A rekurzió folyamata: ˗ a függvény a faktoriális számítását visszavezeti 1-gyel kisebb egész szám faktoriálisának a kiszámítására, amíg lehet. ˗ a számítás elvégzése közben újra és újra meghívja magát, miközben a számítás folytatásához szükséges értékeket és a visszatérési címeket verembe teszi. ˗ a folyamat legalsó szintjét a Faktoriális(0) jelenti, amelynek az értéke definíció szerint 1, itt ér véget a rekurzív hívások sorozata. ˗ ezután folyamatos visszahelyettesítések következnek, a folyamat minden szintjén, és a legfelső szinten meghatározásra kerül n! értéke. Példa n=4 esetén: Faktoriális(4) = 4 * Faktoriális(3) = (verembe: 4, és visszatérési cím) 3 * Faktoriális(2) = (verembe: 3, és visszatérési cím) 2 * Faktoriális(1) = (verembe: 2, és visszatérési cím) 1 * Faktoriális(0) (verembe: 1, és visszatérési cím) Faktoriális(0)=1 1 * Faktoriális(0) (1*1= 1) (veremből: 1, és visszatérési cím) 2 * Faktoriális(1) = (2*1= 2) (veremből: 2, és visszatérési cím) 3 * Faktoriális(2) = (3*2= 6) (veremből: 3, és visszatérési cím) 4 * Faktoriális(3) = (4*6=24) (veremből: 4, és visszatérési cím) Faktoriális(4) = 24

1


___________________________________________________________________________ 1.1.2 Hatvány függvény Rekurzív specifikáció: xn = x * xn -1 ha n > 0 1 ha n = 0 Rekurzív algoritmus: Függvény Hatvány(x: valós, n: egész): valós Ha n > 0 akkor Hatvány := x * Hatvány(x, n-1) különben Hatvány := 1 Függvény vége

1.1.3 Fibonacci sorozat A Fibonacci-sorozat rekurzívan definiált sorozat, a soron következő elemét az előző kettő összegeként kapjuk. A Fibonacci-sorozat első néhány eleme: 0,1,1,2,3,5,8,13,21,34,… Rekurzív specifikáció Fibonaccin := Fibonaccin-1 + Fibonaccin-2 n

ha n > 1 ha n=0 vagy n=1

Rekurzív algoritmus: Függvény Fibonacci(n: egész): egész Ha n > 1 akkor Fibonaccin := Fibonacci(n – 1) + Fibomacchi(n – 2) különben Fbonacchi := n Elágazás vége Függvény vége

A Fibonacci sorozat rekurzív hívásai: Fibonacci(4) Fibonacci(3) + Fibonacci(2) Fibonacci(2) + Fibonacci(1) Fibonacci(1) + Fibonacci(0) Fibonacci(1) + Fibonacci(0) Megjegyzés: látható, hogy a dupla rekurzió miatt sok felesleges függvényhívás történik, vagyis újra kiszámolunk korábban már kiszámolt értékeket. Nagyobb paraméterek esetében a függvény végrehajtása rendkívüli mértékben lelassulhat. A probléma megoldása: a rekurzió feloldása ˗ A Fibonacci-sorozat elemeinek a meghatározásakor megtehetjük, hogy rekurzió helyett iteratív algoritmust alkalmunk, amely a rekurzió gondolatát megtartja, de rekurzió helyett a sorozat korábban kiszámolt elemeit eltároljuk.

2


___________________________________________________________________________ Függvény Fibonacci(n: egész): egész // Nemrekurzív megoldás Ha (n>1) akkor F[0]:=1 // F: egészeket tartalmazó tömb, lokális változóban F[1]:=1 Ciklus i:=2-től n-ig F[i]:=F[i-1]+F[i-2] Ciklus vége Fibonacci:=F[n] különben Fibonacci:=n Függvény vége

1.1.4 Binomiális együttható A matematikában sok helyen alkalmazzuk az ún. Pascal háromszöget: 1 1 1 1 1

1 2

3 4

1 3

6

1 4

1

(0. (1. (2. (3. (4.

sor) sor) sor) sor) sor)

A háromszög 1-től különböző értékeit úgy kapjuk meg, hogy az előző sor két, a számítandó érték fölött elhelyezkedő értékét összeadjuk. Az n. sor k. elemét Bin(n,k)-val jelöljük. Rekurzív specifikáció: Megfigyelhető, hogy: Bin(n,k) =Bin(n-1,k-1) + Bin(n-1,k) 1 Rekurzív algoritmus:

ha ┐((k = 0) vagy (n = k)) ha (k = 0) vagy (n = k)

Függvény Bin(n, k: egész): egész Ha (k > 0) és (k < n) akkor Bin := Bin(n-1, k-1) + Bin(n-1, k) különben Bin := 1 Elágazás vége Függvény vége

Megjegyzés: a dupla rekurzió miatt itt is sok felesleges függvényhívás történik. A rekurzió feloldása ez esetben egy mátrix segítségével oldható meg.

3


___________________________________________________________________________

1.1.5 Hanoi-tornyai Adott 3 pálca, és az egyiken N db korong, különböző méretűek, méret szerint csökkenően, a legnagyobb alul. Feladat: rakosgassuk át a korongokat egy másik pálcára úgy, hogy soha ne tegyünk kisebb korongra nagyobbat. Mindhárom pálcát használhatjuk. Kérdés: Hol a rekurzió ebben a feladatban? Válasz: N korong átrakása visszavezethető kétszer N-1 korong átrakására, közben a legalsó korong áthelyezésére. Specifikáció: n: korongok száma Honnan: melyik pálcáról kell, hogy átrakjuk a korongokat Hová: melyik pálcára kell, hogy átrakjuk a korongokat Mivel: melyik pálca segítségével rakjuk át a korongokat Rekurzív algoritmus: Eljárás Hanoi(n, Honnan, Hova, Mivel) Ha n > 0 akkor Hanoi(n-1, Honnan, Mivel, Hova) Átrak(Honnan,Hová) Ha n > 0 akkor Hanoi(n-1, Mivel, Hova, Honnan) Eljárás vége

1.1.6 Quicksort rendezés Ld. külön fájlban 1.1.7 Maximum-kiválasztás Feladat: Határozzuk meg egy sorozat legnagyobb elemének a sorszámát rekurzívan! Megoldás: Függvény Maxind(A: tömb, N: egész): egész Változó i: egész Ha N > 1 akkor i := Maxind(A, N-1) Ha A[Maxind(A, -1)] > A[N] akkor Maxind := Maxind(A, N-1) Különben Maxind := N Elágazás vége különben Maxind := 1 Elágazás vége Függvény vége

4


___________________________________________________________________________ 2.

A REKURZIÓ HATÉKONYSÁGA

2.1.1 A hatékonyság szempontjainak vizsgálata ˗

˗

˗

Végrehajtási idő o A rekurzív megoldás sokszor feleslegesen, többször számol, vagy hajt végre o Emiatt a végrehajtási idő drasztikusan megnövekedhet o A függvényhívás, paraméterátadás is plusz időt vesz igénybe Tárigény: o A részeredmények tárolása sok helyet foglal (verem) o Gyakran többszörösen is tárolni kell az adatokat o Veremkezelés szükséges a visszatérési címek miatt is Bonyolultság: o A rekurzív algoritmus általában egyszerűbb, néha sokkal egyszerűbb

2.1.2 Rekurzió feloldása Az előzőek miatt egy feladat rekurzív megoldását hatékonyság szempontjából mindig elemeznünk kell, és ha szükséges, akkor célszerű átírni nem rekurzívvá. Ez a rekurzió feloldása. A rekurzió feloldásának általában igényli: ˗ A rekurzió által meghatározott részeredmények eltárolását, tömbben, vagy mátrixban. ˗ A direkt veremkezelést.

5

REKURZIÓ. Rekurzív: önmagát ismétlő valami (tevékenység, adatszerkezet stb.) Rekurzív függvény: függvény, amely meghívja saját magát

Recommend Documents