Rekurzív eljárások

Definíció:

Rekurzív eljárásnak nevezzük azt az eljárást, amely önmagát hívja meg.

Az eljárások ezen típusa ugyan nem tartozik az alaptételek közé, mégis fontos, hogy közelebbről megismerjük ezek működését, mert vannak olyan feladatok, amelyeknél a rekurzív megoldás átláthatóbb, rövidebb programkódot ad, mint az iterációs.

Egy feladatot akkor érdemes rekurzióval megoldani, ha a megoldás során:

• van egy olyan triviális eset, amelyben a megoldás nyilvánvaló
• létezik olyan folyamat, amelynek ismétlése során véges sok lépésben eljutunk az előző pontban tárgyalt esethez.

Nem elhanyagolható, hogy egy rekurzív eljárásban szerepelnie kell valaminek, ami megállítja a folyamatot, hiszen ha nem adjuk meg a leállító feltételt, vagy küszöbfeltételt, végtelen ciklust kapunk.

Nézzünk néhány egyszerűbb feladatot a rekurzió használatára!

Feladat:

Számítsuk ki az első N szám összegét!

A megoldás gondolatmenete a fent leírt rekurzív elvek alapján a következőképpen alakul:

Ha N = 1 akkor

Összeg(1) = 1    'Ez a fent leírt legegyszerűbb eset

egyébként

Összeg(N) = Összeg(N-1)+N    'Ez pedig a folyamat, amit ismétlünk

Elágazás vége

Ebből a pszeudo-kódból azonnal látszik, hogy függvényt kell használnunk a megoldás során.

Program szumma:

Függvény summa(n) : Egész

Ha n = 1 Akkor

summa = 1    'ez a triviális eset

Egyébként

summa = summa(n - 1) + n    'önmagát hívja meg a függvény

Elágazás vége

Függvény vége

Ki: "Meddig adjuk össze a számokat?"

Be: n

Ki: summa(n)

Program vége.

Nézzünk meg két klasszikus példát:

Határozzuk meg a Fibonacci sorozat n. elemét!

Számítsuk ki az n!-t rekurzió segítségével!

Az első feladat megoldása:

A Fibonacci sorozat rekurzív sorozat, amelynek tagjait a következőképpen definiáljuk: a₁ = 1; a₂ = 1; a_n = a_n-1 + a_n-2, ha n >= 3

Program fibonacci:

Függvény fibo(n) : Egész

Ha n = 1 Vagy n = 2 Akkor

fibo = 1

Egyébként

fibo = fibo(n - 1) + fibo(n - 2)

Elágazás vége

Függvény vége

Ki: "Hányadik tagot szeretnéd kiszámolni?"

Be: n

Ki: fibo(n)

Program vége.

A második feladat megoldása:

Az n! matematikai definíciója: n! = 1 * 2 * 3 * … * (n - 1) * n

Program faktorialis:

Függvény fakt(n) : Egész

Ha n = 0 Akkor

fakt = 1

Egyébként

fakt = n*fakt(n - 1)

Elágazás vége

Függvény vége

Ki: "Mely szám faktoriálisára vagy kíváncsi?"

Be: n

Ki: fakt(n)

Program vége.

Házi feladatok:

• Írjunk programot, amely kiszámítja a következő n tagú sor összegét: 1 + 1/2 + 1/3 + 1/4 + … +1/n
• Számítsuk ki egy tetszőleges valós szám N. hatványát!