Rekurzió. Dr. Iványi Péter

Rekurzió Dr. Iványi Péter

1

Függvényhívás void f3(int a3) { printf(”%d”,a3); } void f2(int a2) { f3(a2); a2 = (a2+1); }

SP

void f1() { int a1 = 1; int b1; b1 = f2(a1); } 2

Függvényhívás a1 b1

void f3(int a3) { printf(”%d”,a3); } void f2(int a2) { f3(a2); a2 = (a2+1); }

1 akármi

SP




1 akármi visszatérési cím 1 (argumentum)

SP




a2

1 akármi visszatérési cím 1

SP




a2 SP

1 akármi visszatérési cím 1 visszatérési cím 1 (argumentum)




a2 a3

1 akármi visszatérési cím 1 visszatérési cím 1

SP




a2 a3


SP

void f1() { int a1 = 1; int b1; b1 = f2(a1); }

Ekkor is függvényhívás történik, de most ignoráljuk.

8



a2 a3


SP




a2

1 akármi visszatérési cím 1 visszatérési cím

SP




a2


SP




a2


SP




1 akármi visszatérési cím

SP




1 akármi

SP


Rekurzió, Definíció • Egy értéket vagy egy állapotot úgy definiálunk, hogy definiáljuk a kezdőállapotot, majd általában egy állapotot az előző véges számú állapot segítségével határozzunk meg.

15

A rekurzió célja • A feladat visszavezetése egy még egyszerűbb feladatra egészen addig amíg a feladat olyan egyszerű nem lesz, hogy már megoldható. • Más szóval: a feladat megfogalmazása mindig ugyanaz, így a függvény önmagát hívja de egyre egyszerűbb argumentummal • Előnye: az elegancia. Néhány sorban könnyen érthető kódot írhatunk • Hátránya: Akkor is használjuk ha kevéssé hatékony, sőt pazarló 16

L rendszerek, kitérő • A. Lindenmayer (1925-1989) vezette be mint matematikai eszközt több cellás organizmusok modellezésére

17

Definíció • Az L-rendszerrel leírt modelek dinamikusak abban az értelemben, hogy az eredmény egy térbeli és időbeli folyamat eredménye. • A fejlődést úgynevezett „újraírással” lehet megadni.

18

„Újraírás” • Az újraírás, olyan technika complex objektumok definiálására, ahol egy egyszerű kezdeti objektum részeit egy szabály szerint helyettesítjük újabb objektumokkal. • Újraírási szabály adja meg a hogyant

19

Hópehely • Von Koch 1905

20

Nyelvtanok • Legjobban tanulmányozott újraírási rendszerek karakterekre épülnek • Az első ilyen rendszert Thue adta meg • 1950-es évektől Chomsky munkája meghatározó a formális nyelvtanok területén • Az L-rendszereket Lindenmayer 1968-ban vezette be

21

Különbség • A Chomsky nyelvtan szekvenciálisan, egymás után sorban, alkalmazza az újraírást • Az L-rendszerben az újraírás parallel, egyszerre történik, ezzel is egy celuláris organizmus osztódását szimulálva

22

Példa 1. • Vegyük azokat a szavakat melyek az „a” és a „b” betűkből állnak • Minden betűhöz egy „újraírási szabály” is adva van • a ab • b a • Az újraírás egy alap szóval kezdődik, egy axiómával 23

Példa 2.

24

Grafikus értelmezés • A karaktersorozatok (szavak) „teknős” grafikai parancsok sorozataként is értelmezhetők • Például: – “F”: mozdulj előre – “+”: fordulj balra – “-”: fordulj jobbra

25

Példa • Axióma: F-F-F-F

• Szabály: F

F-F+F+FF-F-F+F

26

Növények 1.

27

Növények 2.

28

Növények 3.

29

Nyomtatás 1. FÜGGVÉNY nyomtat(n) print n HA n != 0 nyomtat(n-1) ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE

nyomtat(3)

à

3210

30

Kiértékelés folyamata Belépés (nyomtat 3) Belépés (nyomtat 2) Belépés (nyomtat 1) Belépés (nyomtat 0) Kilépés Kilépés Kilépés Kilépés

-> -> -> ->

3 2 1 0

31

Megjegyzések a rekurzióról • Orosz baba analógia • Minden alkalommal egy új függvény kerül meghívásra • Lényegében egymásba ágyazott függvények meghívásáról van szó • Csak éppen a függvény mindig ugyanaz • Szekvenciális végrehajtásból következik, hogy az elöző függvény végrehajtása felfüggesztődik amíg az aktuális függvény végrehajtódik 32

Megvalósítás • A program aktuális állapotát egy veremben (stack) mentjük el • Mivel a verem véges mindig biztosítani kell egy végfeltételt, amely a rekurziót leállítja • Ha nincs végfeltétel a program a végtelenségig futna, de mivel a verem véges és hamar megtelik a program hibával leáll.

33

Nyomtatás 2. FÜGGVÉNY nyomtat(n) HA n != 0 nyomtat(n-1) ELÁGAZÁS VÉGE print n FÜGGVÉNY VÉGE

nyomtat(3)

à

Mit fog nyomtatni?

34

Kiértékelés folyamata Belépés (nyomtat 3) Belépés (nyomtat 2) Belépés (nyomtat 1) Belépés (nyomtat 0) Kilépés Kilépés Kilépés Kilépés nyomtat(3)

à

-> -> -> ->

0 1 2 3

0123 35

Rekurzió • Nyomtatás 1: jobb rekurzió – Rekurzív hívás a műveletek után

• Nyomtatás 2: bal rekurzió – Rekurzív hívás a műveletek előtt

36

Általános eset, jobb rekurzió FÜGGVÉNY rekurzív(paraméter) számítás a paraméterrel a paraméter módosítása ... HA feltétel(paraméter) == igaz AKKOR eredmény = kezdőérték KÜLÖNBEN eredmény = rekurzív(paraméter) ELÁGAZÁS VÉGE visszatérési érték: eredmény FÜGGVÉNY VÉGE 37

Mechanizmus 1. • A függvény hívásakor a program a pillanatnyi futási címet a verembe menti, illetve a paramétereket is a veremre teszi. • A meghívott függvény a veremből kiveszi a paramétereket és felhasználja (cím marad). • Amikor vége a függvénynek a visszatérés hatására kiveszi a veremből az elmentett futási címet, majd a mutatott utasítás utáni címen folytatja a program végrehajtását. 38

Mechanizmus 2. • Minden változó lokális, ezért amikor a függvény meghívja önmagát a változóknak egy új példánya jön létre, függetlenül a többitől.

39

Függvényhívás FÜGGVÉNY nyomtat(n) print n HA n != 0 nyomtat(n-1) ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE

SP

40

Függvényhívás FÜGGVÉNY nyomtat(n) print n HA n != 0 nyomtat(n-1) ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE

visszatérési cím 3

SP

nyomtat(3)

41

Függvényhívás FÜGGVÉNY nyomtat(n1=3) print 3 HA 3 != 0 nyomtat(2) ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE

n1


SP

42


n1


SP

43


n1

visszatérési cím 3 visszatérési cím 2

SP

44


n1 n2


SP

45


n1 n2


SP

46


n1 n2 SP

visszatérési cím 3 visszatérési cím 2 visszatérési cím 1

47


n1 n2 SP n3


48


n1 n2 SP n3


49


n1 n2 SP n3

visszatérési cím 3 visszatérési cím 2 visszatérési cím 1 visszatérési cím 0

50

Függvényhívás FÜGGVÉNY nyomtat(n4=0) print 0 HA 0 != 0 nyomtat(n) ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE

n1 n2 SP n3 n4


51


n1 n2 SP n3 n4


52


n1 n2 SP n3 n4


53


n1 n2 SP n3


54


n1 n2 SP n3


55


n1 n2 SP n3


56


n1 n2 SP


57


n1 n2 SP


58


n1 n2 SP


59


n1

SP


60


n1

SP


61


n1

SP


62


SP


63


SP


64

Mikor ne használjuk? • Ha az eredmény zárt alakban is megadható – Pl. számtani sorozat n-edik eleme

• Ha ciklussal is könnyen megoldható a feladat

65

Rekurzió és ciklus • Minden ciklus megvalósítható rekurzióval • Minden rekurzió megvalósítható ciklussal és segédváltozókkal.

66

Lista hossza • Alapeset: Az üres lista hossza: 0 • Rekurzív eset: Egy lista hossza eggyel nagyobb mint a nála eggyel kevesebb elemet tartalmazó lista FÜGGVÉNY hossz(lista) HA lista == üres visszaadott érték: 0 KÜLÖNBEN visszaadott érték: (1 + hossz(listaàkövetkező)) ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE 67

a = hossz(listafej) FÜGGVÉNY hossz(lista) HA lista == üres visszaadott érték: 0 KÜLÖNBEN visszaadott érték: (1 + hossz(listaàkövetkező)) ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE

visszaadott: cím lista

listafej

1.elem

SP

2.elem

NIL 68

FÜGGVÉNY hossz(lista) HA lista == üres visszaadott érték: 0 KÜLÖNBEN visszaadott érték: (1 + hossz(listaàkövetkező)) ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE

visszaadott: cím lista

listafej

1.elem

SP

2.elem

NIL 69


visszaadott: cím lista visszaadott: cím lista SP

listafej

1.elem

2.elem

NIL 70


visszaadott: cím lista visszaadott: cím lista SP

listafej

1.elem

2.elem

NIL 71


visszaadott: cím

SP

lista visszaadott: cím lista visszaadott: cím lista

listafej

1.elem

2.elem

NIL 72


visszaadott: cím

SP

lista visszaadott: cím lista visszaadott: cím lista

listafej

1.elem

2.elem

NIL 73


visszaadott: cím

SP

lista visszaadott: cím lista visszaadott: 0 cím lista

listafej

1.elem

2.elem

NIL 74


visszaadott: cím

SP


listafej

1.elem

2.elem

NIL 75


visszaadott: cím

SP


listafej

1.elem

2.elem

NIL 76


visszaadott: cím

SP

lista visszaadott: 1 cím lista visszaadott: 0 cím lista

listafej

1.elem

2.elem

NIL 77


visszaadott: cím

SP


listafej

1.elem

2.elem

NIL 78


visszaadott: cím

SP


listafej

1.elem

2.elem

NIL 79


visszaadott: 2 cím

SP


listafej

1.elem

2.elem

NIL 80


visszaadott: 2 cím

SP


listafej

1.elem

2.elem

NIL 81

FÜGGVÉNY hossz(lista) HA lista == üres visszaadott érték: 0 KÜLÖNBEN visszaadott érték: (1 + hossz(listaàkövetkező)) ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE a = 2

SP

visszaadott: 2 cím lista visszaadott: 1 cím lista visszaadott: 0 cím lista

listafej

1.elem

2.elem

NIL 82

Rekurzió többszörös alapesettel • Elem keresése egy listában – Alapeset 1: Ha üres a lista, az elem nincs benne – Alapeset 2: Ha az elem egyenlő a lista adat részével akkor megvan – Rekurzív eset: Egyébként keressük a lista maradék részében

83

Elem keresése egy listában FÜGGVÉNY keres(obj, lista) HA lista == üres visszaadott érték: HAMIS KÜLÖNBEN HA listaàadat == obj visszaadott érték: IGAZ KÜLÖNBEN visszaadott érték: keres(obj, listaàkövetkező) ELÁGAZÁS VÉGE ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE

84

Többszörös rekurzív eset • Elem minden előfordulását töröljük egy listából – Alapeset: Ha üres a lista, az elem nem törölhető – Rekurzió 1: Ha az elem egyenlő a lista adat részével akkor csak maradék résszel kell folytatni – Rekurzív 2: Egyébként olyan listát kell visszaadni ami tartalmazza az adat részt és a listát amiből még törlünk

85

Elem törlése listából FÜGGVÉNY torol(obj, lista) HA lista == üres visszaadott érték: NIL KÜLÖNBEN HA listaàadat == obj visszaadott érték: torol(obj, listaàkövetkező) KÜLÖNBEN visszaadott érték: listaàkovetkezo = torol(obj, listaàkövetkező) ELÁGAZÁS VÉGE ELÁGAZÁS VÉGE FÜGGVÉNY VÉGE

86

Rekurzió. Dr. Iványi Péter

Recommend Documents