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 [e :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 :n
ha :n > 0 [jrekurzív :n - 1]
vége
Balrekurzió
eljárás brekurzív :n
ha :n > 0 [ rekurzív :n - 1]
elem :n
vége
Többszörös rekurzió
eljárás trekurzív :n
...
ha :n > 0 [trekurzív :n - 1]
...
ha :n > 0 [trekurzív :n - 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 :n :h
ism 4 [ e :h j 90 ]
j 90 e :h b 90
ha :n > 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
