# 8. hét: rekurzió

Czirkos Zoltán · 2025.10.12.

Laborfeladatok a rekurzió témakörében. Sorozatok rekurzív definíciója. Báziskritériumok és egyszerűsítési lépések. Egyszerű rekurzív ábrák elkészítése teknőcgrafikával.

Felkészülés a laborra:

- A rekurzióról szóló előadás áttekintése.
- A nyomkövetésről tanultak átismétlése.

## 1. Faktoriális

Tanultad, hogy egy n szám faktoriálisát így is lehet definiálni:

         ┌
         │ 1,        ha n = 0
    n! = ┤
         │ n·(n-1)!, ha n > 0
         └

Fogj egy papírlapot, és fejtsd ki n! értékét kézzel, az alábbi módon! Vagyis helyettesítsd be a faktoriális definíciója szerint megadott szabály szerint a kifejezést.

    6! = 6 * 5!
       = 6 * 5 * 4!
       ...

Ha ezzel megvagy, írj Python programot, amely egy rekurzív faktoriális függvényt tartalmaz! Vagyis térjen ez vissza `1`-gyel, ha a paramétere `0`, és `n * fakt(n-1)`-gyel, ha nagyobb. Teszteld a megírt függvényed, írd vele ki a faktoriálisok értékét 0-tól 10-ig!

    0! = 1
    1! = 1
    2! = 2
    3! = 6
    4! = 24
    5! = 120
    6! = 720
    7! = 5040
    8! = 40320
    9! = 362880
    10! = 3628800

Vigyázz: rekurzív függvényt kell írnod, ebben nem kell ciklus, se `while`, se `for`. Változó sem lesz benne. A `main()`-ben viszont lehet.

Megoldás

    def fakt(n):
        if n == 0:
            return 1
        else:
            return n * fakt(n - 1)

    def main():
        for i in range(0, 10+1):
            print(f"{i}! = {fakt(i)}")

    main()

## 2. A rekurzió nyomkövetése

Engedélyezd most a nyomkövetést a laboron tanult módon. Figyeld meg, hogyan hívja a függvény saját magát a `fakt(6)` kifejezés kiértékelése közben. Az IDLE nyomkövető az ablak felső részében mutatja a függvényhívásokat:

Az egyes hívásokra kattintva alul látszik, hogy azokhoz milyen paraméter tartozik.

## 3. Fraktál

Tanulmányozd az alábbi rajzot!

A legfelső sorban egy szimpla vonalat látsz. Képzeld azt, hogy a szimpla vonalat 3 egyenlő hosszúságú darabra töröd (ahol a jelek vannak), és a középső részt egy 60 fokos háromszöggel helyettesíted. Vagyis megteszed az 1/3 hosszt, aztán balra fordulsz 60 fokot, újabb 1/3, jobbra fordulás, újabb 1/3, és végül balra fordulás, befejező 1/3. Így alakult ki a második rajz. Ha a második rajz összes szakaszát helyettesíted saját magával, akkor jutsz a harmadik rajzhoz.

Egy olyan rekurzív függvényt kell írnod, amely ezt a rajzot elkészíti teknőcgrafikával. A gondolatmenet a következő:

- A függvény paraméterként kap egy hosszt (h), és a rajz bonyolultságát (n).
- Ha a legegyszerűbb esetet kell megrajzolni (n = 0), akkor csak húz egy egyenes szakaszt.
- Ha egy bonyolultabb esetet, akkor pedig bejárja a szakasz-fordulás-szakasz-fordulás-szakasz-fordulás-szakasz útvonalat, megrajzolva ezt a formát: `_/\_`.
- Ahol viszont szakaszt kell rajzolnia, oda nem szakaszt rajzol, hanem az eggyel egyszerűbb ábrát: `n-1`.

Előbb készítsd el azt a változatot, amelyik csak a középső ábrát rajzolja ki, utána egyszerű a szakaszok rajzolását rekurzív hívásra cserélni!

Megoldás

Lásd a következő feladatnál.

## 4. Hópehely

Rajzolj hópelyhet az előző feladat fraktáljával! Ehhez nincs más dolgod, mint három fraktált egymás mellé tenni, egymáshoz képest 120 fokkal elforgatva (lásd a bal felső rajzot). Minél nagyobb a bonyolultság, annál szebb lesz a hópehely.

Valósítsd meg ezt egy `hopehely(hossz, bonyolultság)` paraméterű függvényben! Használd fel ehhez az előző fraktál függvényt, változatlan formában!

Megoldás

    import turtle

    def fraktal(h, n):
        if n == 0:
            turtle.forward(h)
        else:
            fraktal(h / 3, n - 1)
            turtle.left(60)
            fraktal(h / 3, n - 1)
            turtle.right(120)
            fraktal(h / 3, n - 1)
            turtle.left(60)
            fraktal(h / 3, n - 1)

    def hopehely(h, n):
        for _ in range(3):
            fraktal(h, n)
            turtle.right(120)

    def main():
        turtle.speed(0)
        hopehely(300, 4)
        turtle.done()

    main()

## 5. Számtani sorozat

Egy számtani sorozatot (jelöljük most `S`-sel) annak első tagjával és növekményével definiáljuk. Az első tag `S0` értéke `a`, a többi tagot pedig úgy számítjuk ki, hogy mindig az előző taghoz hozzáadjuk `d`-t, a növekményt:

         ┌
         │ a,        ha i = 0
    Si = ┤
         │ Si-1 + d, ha i > 0
         └

Írj rekurzív függvényt, amelyik megkapja 1) a sorozat első tagját: `a`, 2) a sorozat növekményét: `d`, és 3) hogy a sorozat hányadik elemét kell megadja: `i`, és visszatér `Si` értékével! Alkalmazd a függvény megírásakor a fenti rekurzív definíciót! Egészítsd ki a megírt függvényt egy főprogrammal, amelyben kiírod egy számtani sorozat első 10 elemét!

A főprogramban lehet ciklus, de a sorozatot megadó függvényben ne legyen se `while`, se pedig `for`!

Megoldás

    def szamtani(a, d, n):
        if n == 0:
            return a
        else:
            return szamtani(a, d, n-1) + d

    def main():
        for i in range(0, 10):
            print(szamtani(5, 3, i))

    main()

## 6. Gyors hatványozás

A hatványozás elvégezhető annál gyorsabban is, mintha a kitevőnek megfelelő számú szorzást csinálnánk. Pl. `a8 = a4·a4`, `a4 = a2·a2` és `a2 = a·a` miatt a nyolcadikra hatványozáshoz mindössze három szorzásra van szükség. A következő megfigyelést tehetjük:

         ┌
         │ (a·a)k/2, ha k páros
    ak = ┤
         │ a·ak-1, ha k páratlan.
         └

Írj rekurzív függvényt, amely a fentiek alapján végzi el a hatványozást! Paraméterei legyenek az alap és a kitevő, visszatérési értéke pedig a hatvány. Írd ki kettő első tizenhat hatványát!

A rekurzív függvénybe most se tegyél ciklust, dolgozz a definíció alapján! Ahhoz, hogy ez működjön, még egy báziskritériumot be kell vezetned, amit a fenti definíció nem tartalmaz. Mi lehet az?

Megoldás

A szükséges báziskritérium: ha `k == 0`, akkor a hatvány értéke `1`. Vagyis annak rögzítése, hogy bármelyik szám 0. hatványa 1. A rekurzióban közeledünk ehhez a báziskritériumhoz, mert mindig felezzük a kitevőt, vagy levonunk belőle 1-et.

A `k == 1` esetet is vehetnénk báziskritériumnak, de a `k == 0` még jobb, még ha nem is tűnik intuitívnak elsőre. Így legalább arra is működik a program. `a1` értéke így `a * a0` módoon számítódik ki.

    def gyorshatvany(a, k):
        if k == 0:
            return 1
        if k % 2 == 0:
            return gyorshatvany(a * a, k // 2)
        else:
            return a * gyorshatvany(a, k - 1)

    def main():
        for k in range(0, 16):
            print(gyorshatvany(2, k))

    main()

## 7. Számrendszer váltó

Írj függvényt, amely paraméterként kap egy pozitív egész számot valamint egy számrendszert, és kiírja a képernyőre a számot a megadott számrendszerben! Elég most, ha csak 10-es számrendszerig működik. A megoldáshoz használj rekurziót! Miért sokkal egyszerűbb ez a megoldás, mint az iteratív?

Tipp

Ennek a feladatnak a megoldásához a fordított kiírás ad ötletet. Pl. a 123-at 10-es számrendszerben úgy kell kiírni, hogy előbb kiírjuk a 123/10-et (12), utána pedig a 123%10-et (3). A rekurzióval ez a fordított sorrend könnyen előállítható.

## 8. Három számjegyenkénti felosztás

Írj függvényt, amely a paraméterként kapott pozitív egész számot három számjegyenként csoportosított formában írja ki. Pl.: 16 077 216. Próbáld ki más számokra is: 999, 1000, 12, 0, 1000222!

Tipp

Használj rekurziót! Ez olyan, mintha ezres számrendszerben írnál ki.

## 9. Járda kövezése

Hányféleképpen lehet egy adott hosszúságú járdát kikövezni 1 és 2 méter hosszúságú járdalapokkal? Például ha 3 méteres a járda, a lehetőségek: 1+1+1, 1+2, 2+1, tehát összesen 3.

Tipp

A megoldás alapötlete a következő. Kétféle járdalap van (az 1 és a 2 méter hosszú), ami azt jelenti, hogy induláskor két lehetőség van: vagy egy 1 méteressel, vagy egy 2 méteressel kezdődik a járda. Ha összesen 10 métert kell haladni, az első esetben már csak 9, a második esetben pedig már csak 8 métert kell majd haladni. A 9 méteres és a 8 méteres szakasz kövezése is megoldható valahányféleképpen. A 10 méter hosszú járdához a megoldások számát a kettő összege fogja adni.

Már csak alkalmas báziskritériumok kellenek. A függvény egyre kisebb számokkal fogja meghívni magát (a `hossz - 1` és a `hossz - 2`). Írjuk fel báziskritériumként azokat az eseteket, amelyeket már nem lehetne tovább egyszerűsíteni, mivel nulla vagy negatív hossz keletkezne a hívásban! Ezek:

- 1 hosszúságú járdát egyféleképpen tudunk kirakni (1 méteres lappal), illetve
- 2 hosszúságú járdát pedig kétféleképpen (2 méteres és 1+1 méteres lapokkal).

Megoldás

A báziskritériumok meghatározásakor másképp is gondolkodhatunk. A jelenlegi megoldás nem túl általános, mivel ezek a báziskritériumok függenek az egyszerűsítési lépésektől is (a lapok hosszától). Helyettük vehetjük báziskritériumnak azokat az eseteket, amikor az egyszerűsítés ténylegesen 0 értékű, vagy akár negatív hosszhoz jut:

- Ha 0 hosszúságú járdánk van, az egy (vigyázat, nem nulla!) módon kövezhető csak: úgy, hogy nem csinálunk semmit.
- A fenti függvény láthatóan meghívja magát negatív hosszakra is, negatív hosszúságú járda viszont nem létezhet, ezért olyankor 0 megoldás van.

A feladatnak ez is jó megoldása:

    def jarda(hossz):
        if hossz < 0:
            return 0    # lehetetlen
        if hossz == 0:
            return 1    # nem csinálunk semmit

        return jarda(hossz - 1) + jarda(hossz - 2)

Ez azért is jobb, mert a lapok hosszai most csak az egyszerűsítési lépésben szerepelnek.