Logo‎ > ‎Elmélet‎ > ‎

Rekurzív eljá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

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 :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 [ brekurzí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 :j 90 ]
    j 90 e :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

eljá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 fa

eljá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

Sierpinski-háromszög

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