Gyakorlat, 10. hét: rekurzió

Czirkos Zoltán · 2023.10.31.

Rekurzív algoritmusok: rekurzió tervezése, triviális esetek és visszavezetések.

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:

1. Ötödik kis ZH

Ezen az órán van az ötödik kis ZH.

2. 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, 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!

Megoldás

A matematikában ak formában jelölt hatványozást a programunkban egy függvénnyel implementáljuk: hatvany(a, k).

Észrevehetjük, hogy a feladat szövegében felírt esetszétválasztás éppen a rekurzióban használt egyszerűsítési lépéseket adja meg. Mindkét esetben haladunk a kisebb hatványkitevők felé, vagy eggyel kisebb kitevőt használva, vagy felezve azt. Így van szükségük egy hatvany(alap * alap, kitevo / 2) vagy hatvany(alap, kitevo - 1) függvényhívásra.

Még egy báziskritériumot meg kell találnunk, amiről a feladat nem beszél: minden számnak a nulladik hatványa 1.

#include<stdio.h>

double hatvany(double alap, unsigned kitevo) {
    /* barminek a nulladik hatvanya 1 */
    if (kitevo == 0)
        return 1;

    if (kitevo % 2 == 0)
        /* ha paros, akkor alap negyzetre, kitevo felezve */
        return hatvany(alap * alap, kitevo / 2);
    else
        /* amugy alap * alap a k-1-ediken */
        return alap * hatvany(alap, kitevo - 1);
}

int main(void) {
    for (int i = 0; i < 16; ++i)
        printf("%d %g\n", i, hatvany(2, i));

    return 0;
}

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

Megoldás

A megoldás alapötlete a következő. Kétféle járdalapunk van (az 1 és a 2 méter hosszú), ami azt jelenti, hogy induláskor két lehetőségünk van: vagy egy 1 méteressel, vagy egy 2 méteressel kezdünk. 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 haladnunk.

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.

A rekurzióban az egyszerűsítési lépést így ez a kódrészlet adja:

int jarda(int hossz) {
    /* ... */
    return jarda(hossz - 1) + jarda(hossz - 2);
}

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

A megoldás:

#include <stdio.h>

/**
 * Visszaadja, hányféleképpen lehet lekövezni egy
 * <hossz> méret hosszú járdát 1 és 2 méteres kövekkel.
 */
int jarda(int hossz) {
    if (hossz == 1)
        return 1;   /* 1 */
    if (hossz == 2)
        return 2;   /* 1+1 és 2 */

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

int main() {
    int h;
    printf("Hossz?\n");
    scanf("%d", &h);

    printf("%d lehetőség.\n", jarda(h));
}

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:

int jarda(int 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. Így akár vehetnénk azokat tömbből is, vagy megadhatná azt akár a felhasználó is, futási időben.

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

Megoldás

A lényeg: mindig összegezni kell a lehetséges megoldásokat. A báziskritériumok változatlanok, ha negatívra és nullára építettük őket:

int jarda(int hossz, int hanyfele) {
    if (hossz < 0)
        return 0;
    if (hossz == 0)
        return 1;
    
    int osszeg = 0;
    for (int i = 1; i <= hanyfele; ++i)
        osszeg += jarda(hossz - i, hanyfele);
    return osszeg;
}

4. Permutáció

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

Megoldás

Az olvashatóság kedvéért az alábbi magyarázatban minden számsort egybe fogunk írni. De az 1234 alatt valójában egy négyelemű tömböt értünk: {1, 2, 3, 4}.

Tegyük fel, hogy kezdetben a számsor 1234. Ennek a permutációi kezdődhetnek 1-gyel, 2-vel, 3-mal és 4-gyel. Az 1-gyel kezdődőek: 1234, 1243, 1324, … ezek végülis egy fix 1-esből, és utána a 234 számsor permutációiból épülnek fel. A 2-vel kezdődőek: 2134, 2143, 2314, …, vagyis a 2-es szám, és az 134 számsor permutációi. Itt van ebben a rekurzió! Az 1234 számsor permutációi mindig a számsor valamely elemével kezdődnek, és az utána fennmaradó tömbrészlet permutációival kell azokat kiegészíteni.

A permutáló függvény az összes sorrend előállítását úgy valósítja meg, hogy a kapott tömb mindegyik elemét berakja az első helyre (vagyis mindegyik elemet megcseréli az elsővel), és utána képezi a fennmaradó rész permutációit. Ha nincs fennmaradó rész, akkor pedig kiírja az addigra már összekevert számsort. Pl. a kiindulási számsor 1234, akkor:

  • először az 1[234]-eket írja ki (csere nélkül)
  • utána pedig cserékkel: 2[134] (i=1), 3[214] (i=2), 4[231] (i=3), és mindenhol a szögletes zárójellel jelzett részre rekurzívan hívódik.

A rekurzió itt azért is jó, mert miután visszajöttünk a fennmaradó rész permutációinak képzéséből, akkor emlékezzünk rá, hogy melyik elemeket kell visszacserélni (ez lokális változó, eltárolódik a veremben).

#include <stdio.h>

/* megcsereli az adott indexu elemeket */
void cserel(int *tomb, int a, int b) {
    int t = tomb[a];
    tomb[a] = tomb[b];
    tomb[b] = t;
}

/* kiirja a tomb szamait egy sorba */
void kiir(int *tomb, int hossz) {
    for (int i = 0; i < hossz; ++i)
        printf("%d ", tomb[i]);
    printf("\n");
}

void permutal(int *tomb, int hossz, int start) {
    if (start == hossz-1) {
        /* ha mar nincs mit permutalni */
        kiir(tomb, hossz);
    } else {
        /* permutaljuk a tomb hatralevo reszet, tovabba minden
         * szamot megcserelunk a startadikkal, es ugy is
         * permutalunk. az elso esetet, amikor i=start lenne,
         * kulon is lehet venni, mivel olyankor nem kell csere. */
        permutal(tomb, hossz, start+1);

        for (int i = start+1; i < hossz; ++i) {
            cserel(tomb, start, i);    /* csere */
            permutal(tomb, hossz, start+1);
            cserel(tomb, start, i);    /* visszacsere */
        }
    }
}

int main(void) {
    int szamok[] = {1, 2, 3, 4};
    permutal(szamok, 4, 0);
    return 0;
}

A fenti megoldás nem veszi figyelembe azt, ha egyforma elemek vannak a tömbben, és azokat is cseréli. Pl. az 1221 számsornak többször is megjelennek ugyanazon permutációi. Ehhez a cserék előtt meg kell vizsgálnunk azt, hogy a cserélendő szám szerepelt-e már a cserések között. Mert ha igen, akkor azt a lépést nem kell újra elvégezni, hanem ki kell hagyni:

permutal(szam, hossz, start + 1);

for (int i = start + 1; i < hossz; ++i) {
    /* volt mar ez a szam? */
    bool volt_mar = false;
    for (int k = start; k < i; ++k)
        if (szam[k] == szam[i])
            volt_mar = true;
    /* akkor kihagyjuk */
    if (volt_mar)
        continue;
    
    /* amugy pedig, ahogy eddig */
    cserel(szam, start, i);    /* csere */
    permutal(szam, hossz, start + 1);
    cserel(szam, start, i);    /* visszacsere */
}

5. Pénzváltás

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

Megoldás

A probléma könnyen megoldható rekurzívan. Tekintsünk pl. egy 20 forintost! Két lehetőségünk van: ha a 20 forintos része a megoldásnak (vagyis adunk egy 20-ast), akkor a maradék 100-20=80 forintot még valahányféleképpen (x) ki lehet fizetni. A másik lehetőség, ha azt mondjuk, hogy nem adunk 20-ast, és a 100 forint kifizetését a többi érmével oldjuk meg (y lehetőség). A megoldás ezek összege: x+y.

Így közeledünk a rekurzióban a báziskritérium felé: vagy az összeg csökken, vagy a felhasználható érmefajtákat csökkentjük. Figyelembe kell még vennünk három extrém esetet. Ezek lesznek a báziskritériumok:

  1. Ha 0 forintot kell kifizetnünk, azt egyféleképpen tehetjük: nem adunk pénzt.
  2. Ha 0-nál többet kell fizetnünk, de nincs semmilyen fajta érménk, akkor nulla lehetőség.
  3. Ha negatív összeget kell fizetnünk, azt sem tudjuk megtenni: nulla lehetőség.

Az utóbbi feltételt az algoritmus egyszerűségéhez használjuk ki. Jelentése: ha 5 forintot kell kifizetni, és megpróbáljuk egy 20-assal, akkor még -15 forintot kellene – de ez nem megoldás.

#include <stdio.h>
#include <stdlib.h>

int penzvalto(int mennyit, int *fajtak, int hanyadiktol) {
    /* báziskritérium */
    if (mennyit == 0) // 1. pont
        return 1;
    if (fajtak[hanyadiktol] == -1 || mennyit < 0) // 2, 3. pont
        return 0;

    /* egyszerűsítés */
    return penzvalto(mennyit-fajtak[hanyadiktol], fajtak, hanyadiktol)
           + penzvalto(mennyit, fajtak, hanyadiktol+1);
}

int main(void) {
    int fajtak[] = {5, 10, 20, 50, -1};

    printf("Összesen: %d lehetőség\n", penzvalto(100, fajtak, 0));

    return 0;
}

Az érmék névértékeit egy tömbbe tettük, amely egy lezáró -1-et is tartalmaz (a római számos példákhoz hasonlóan). A függvény ezt a tömböt kapja, és egy indexet, hogy hányadik elemtől kell a tömböt figyelembe vegye. Az utolsó sorában ezt növeli, és úgy hívja meg magát – így maradnak ki a tömb eleji érmék a rekurzív hívásban, és így fogy el végül a tömb, amikor fajtak[hanyadiktol]==-1. Ez megoldható lenne pointer aritmetikával is: fajtak+1 a tömb belsejébe mutat (a hátsó részére), és így fogyhat el a tömb.

Fontos figyelembe venni, hogy itt a pénzérmék sorrendje nem számít; pl. 10+5+5 ugyanaz a megoldása 20 forint kifizetésének, mint az 5+5+10 vagy az 5+10+5. Az ilyen megoldásokat egynek számolja a program, mégpedig amiatt, hogy az egyszer már átlépett érmét (hányadiktól+1 értékű paraméter) nem próbálja meg felhasználni többször. Így például nem számolja bele a 10+5+5 megoldást (ahhoz a 10-estől visszafelé kellett volna indulni), és az 5+10+5-öset sem.