NézetNyomtat

Rekurzív eljárások

Rekurzív ejárások

A rekurzió fogalma

értelmező kéziszótár :: rekurzió --> lásd : rekurzió
Kevésbé humorosan: a rekurzív problémamegoldás lényege, hogy a feladatot kisebb, az eredetihez hasonló részfeladatokra bontjuk, és azok (szintén rekurzív módon megkapott) megoldásából állítjuk össze az eredeti feladat megoldását. Ahhoz, hogy módszerünk eredményt adjon, kell egy olyan szint, ahol már nem kell tovább bontani a problémát, hanem direkt módszerrel megoldható.

Matematikai példa

Ha n elem közül k-t kell kiválasztanunk, ezt ${n\choose k}$-féle módon tehetjük meg. A binomiális együtthatók a következő rekurzióval számolhatók: ${n\choose k}={{n-1}\choose {k-1}}+{{n-1}\choose k}$, ha $n\ge 1, 0\lt k \lt n$, és ${n\choose k}=1$, ha $k=0$, vagy $k = n$, vagy $n=0$.

Rekurzív ábrák

A rekurzív ábrák részként tartalmaznak egy az egészhez hasonló alakzatot.
eljárás reknégyzet :h
    ism 4 [:h j 90]
    ha :h>1 [reknégyzet :h/1.5] 
vége 

Rekurziós sémák

A rekurzív eljárások olyan eljárások, amelyek meghívják önmagukat. Ha el akarjuk kerülni a végtelen ciklust, paraméterezzük a rekurzív eljárásokat, és a rekurzív hívást egy feltételtől tegyük függővé.

Jobbrekurzió

Egy "elem" eljárást hívunk meg egyre kisebb :n paraméterrel. Ha a paraméter értéke nullára csökken, nem folytatódik a rekurzió.
eljárás jrekurzív :n
    elem :
    ha :> 0 [jrekurzív :- 1]
vége 

Balrekurzió

eljárás brekurzív :n
    ha :> 0 [ rekurzív :- 1]
    elem :n
vége 

Többszörös rekurzió

eljárás trekurzív :n
    ...
    ha :> 0 [trekurzív :- 1]
    ...
    ha :> 0 [trekurzív :- 1]
    ...
vége 

Példák rekurzióra

Egyszerű ismétlés

Ha egy alakzatot :n-szer akarunk kirajzolni, a rekurzió paraméterével tudjuk :n értékét szabályozni.
eljárás irek ::h
    ism 4 [ e :h j 90 ]
    j 90 e :h b 90
    ha :> 0 [irek :n-1 :h]
vége
Az irek 10 30 hívás eredménye:

Ismétlés és változás

Szögletes csigavonal

Torony

Bináris fa

Koch-görbe