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
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 [ brekurzí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 csigavonaleljárás spirál :h :n
ha :n > 0[
e :h j 90 spirál :h+10 :n-1
]
vége
A következő ábra a spirál 10 15 hívás eredménye: Torony
Bináris faeljárás fa :H :N
HAK :N = 0 [ E :H H :H]
[
E :H
B 45 fa :H/2 :N-1
J 90 fa :H/2 :N-1
B 45
H :H
]
vége
A következő ábra a fa 120 5 hívás eredménye:
Koch-görbe
eljárás sierpinski :h :n
ha :n > 0 [
b 30
ism 3 [
e :h/2 b 90 sierpinski :h/2 :n-1
j 90 e :h/2
j 120
]
j 30
]
vége
Az ábra a sierpinski 300 6 hívással készült. Pitagorasz-fa |