Gyakorlat, 8. hét: rekurzió

A rekurzióhoz

Rekurzív algoritmusoknál két dolgot kell meggondolnunk:

• A triviális eseteket, amelyeknél a megoldás magától értetődik. (Pl. üres sztring hossza nulla.)
• Nem triviális esetben azt, hogy hogyan tudjuk a kapott problémát visszavezetni egyszerűbb problémákra. (Pl. nem üres sztring hossza 1 + a sztring hossza a második betűtől kezdve.)

Az előbbi a báziskritérium, az utóbbi pedig az egyszerűsítési lépés a rekurzióban, amellyel minden rekurzív függvényhívásnál a báziskritérium felé haladunk. Keressük meg ezeket az alábbi problémáknál!

Felkészülés a gyakorlatra:

• A rekurzióról szóló előadás anyagának megértése.

Ezen az órán van a negyedik kis ZH.

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, továbbá a4 = a2·a2, és végül 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:

• ak = ak/2·ak/2 = (a·a)k/2, ha k páros, és
• ak = a·ak-1, ha k páratlan.

Írjunk 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 keresett hatvány!

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.

Hogyan kell módosítani a programot, ha 3 egység hosszú lapunk is van?

Hogyan, ha paraméterként kapjuk, hogy hányféle lap van? (Pl. 5 → 1, 2, 3, 4, 5 hosszú lapok vannak.)

Írjuk ki egy egész tömbnek (számsornak) az összes permutációját, azaz lehetséges sorrendezését! Pl. 123 permutációi: 123, 132, 213, 231, 312, 321.

Adott egy zsák 5, 10, 20 és 50 forintos érménk. Hányféleképpen lehet ezekkel kifizetni 100 forintot?

(A feladat nehezített változata megtalálható a feladatgyűjteményben.)