8. hét: rekurzió

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.

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.

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.

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!

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!

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!

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?

Í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ó.

Í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.

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).

Ha a laborfeladatokkal elkészültél, dolgozz a példatárban lévő feladatokon, a szorgalmi feladatokon, a minta vizsgán, vagy a házi feladatodon.

Informatikusok próbálják lekódolni az Algoritmusok és gráfok tárgyon tanult algoritmusokat. Ezzel két legyet lehet ütni egy csapásra, mert két tantárgyat is gyakoroltok egyszerre.