9. gyakorlat: rekurzió

A rekurzió nélkül lehetetlennek tűnő feladat rekurzív megoldása végtelenül egyszerű. Az aktuális pontot kifestjük, és utána mind a négy irányba megpróbálunk menni. Ha valamerre sikerül, ott ugyanaz lesz a feladat: az aktuális pontot kifesteni, és mind a négy irányba megpróbálni menni. Ha a festés ilyen módon végül egy zsákutcában elakad, a függvények visszatérnek – és a próbálkozás megy tovább a másik három lehetséges irányba.

#include <stdio.h>

void kifest(char kep[20][32], int y, int x)
{
   kep[y][x]='x';
   if (y>0 && kep[y-1][x]!='x') kifest(kep, y-1, x);
   if (y<19 && kep[y+1][x]!='x') kifest(kep, y+1, x);
   if (x>0 && kep[y][x-1]!='x') kifest(kep, y, x-1);
   if (x<30 && kep[y][x+1]!='x') kifest(kep, y, x+1);
}

int main()
{
   /* IDE KELL BERAKNI A RAJZOT */
   int y;
   
   kifest(z4qqq, 10, 10);
   for (y=0; y<20; ++y)
      puts(z4qqq[y]);
   
   return 0;
}

#include <stdio.h>

void kozvetlen(double t[], int db) {
    int j, minindex;
    
    /* ha a tömbben nincs két elem, akkor csak rendezett lehet */
    if (db < 2)
        return;
 
    minindex=0;                /* minimum keresése */
    for (j=1; j<db; ++j)
        if (t[j]<t[minindex])
            minindex=j;
    if (minindex!=0) {         /* csere? */
        double temp=t[minindex];
        t[minindex]=t[0];      /* csere. */
        t[0]=temp;
    }

    /* a tömb fennmaradó részének rendezése */
    kozvetlen(t+1, db-1);
}


int main()
{
    double tomb[]={6, 9, 3, 7, 8, 5, 5.76};
    int i;
    
    kozvetlen(tomb, 7);
    for (i=0; i<7; ++i)
        printf("%g ", tomb[i]);
    
    return 0;
}

A megoldás lényege, hogy egy-egy betűpárt megcserél, és a fennmaradó részeket is permutálja. A start változóban azt kapja a függvény, hogy hányadik karaktertől kezdve kell kezdeni a permutálást. Ha ez megegyezik a sztring hosszával, akkor már nem permutál (hiszen már nincs mit), hanem egyszerűen kiírja az aktuális állapotot. Ez a báziskritérium, így lesz vége a rekurzió „mélységének” – a rekurziónál mindig kell lennie egy feltételnek, amikor többé már nem hívja meg magát a függvény. Minden hívásnál közelít efelé a bázis felé, hiszen mindig egyre rövidebb fennmaradó sztringrészletet permutál.

Tegyük fel, hogy kezdetben a sztring „abcd”. Ennek úgy néznek ki az anagrammái, hogy azok kezdődhetnek a-val, b-vel, c-vel és d-vel. Az a-val kezdődőek: „abcd”, „abdc”, „acbd”, … ezek végülis egy fix „a”, és utána a „bcd” sztring anagrammái, az összes lehetséges sorrendben. A b-vel kezdődőek: „bacd”, „badc”, „bcad”, …, vagyis egy „b” betű, és az „acd” sztring anagrammái. Itt van ebben a rekurzió: az „abcd” sztring anagrammái azok kezdődnek az „abcd” sztring valamelyik (egyik) karakterével, és utána fennmaradó karakterek (de már csak három betűs sztring) anagrammái kellenek.

A permutáló függvény ezt úgy valósítja meg, hogy a kapott sztring mindegyik karakterét berakja az első helyre (vagyis mindegyik karakterét megcseréli az elsővel), és utána képezi a fennmaradó rész anagrammáit. Ha nincs fennmaradó rész, akkor pedig kiírja az addigra már összekevert sztringet. Pl. a kiindulási sztring „abcd”, akkor:

• először az a[bcd]-ket írja ki (csere nélkül)
• utána meg cserékkel: b[acd] (i=1), c[abd] (i=2), d[abc] (i=3), és mindenhol a [] részre rekurzívan hívódik.

Az összes hívás az első mélységben így, ahol a [] jelenti a további rekurzív hívásokat:

• a[bcd] (nincs csere)
• b[acd] (a↔b)
• c[bad] (a↔c)
• d[bca] (a↔d)

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

#include <stdio.h>
#include <string.h>
 
/* megcsereli az adott indexu karaktereket */
void betucserel(char* str, int a, int b)
{
    char t=str[a];
    str[a]=str[b];
    str[b]=t;
}
 
void permutal(char* str, int start)
{
    int hossz=strlen(str);
    
    if (start==hossz-1)
        printf("%s ", str);    /* ha mar nincs mit permutalni */
    else {
        int i;
 
        /* permutaljuk a string hatralevo reszet, tovabba minden
         * karaktert megcserelunk a startadikkal, es ugy is
         * permutalunk. az elso esetet, amikor i=start lenne, kulon
         * is lehet hivni, mivel olyankor nem kell csere. */
        permutal(str, start+1);

        for (i=start+1; i<hossz; ++i) {
            betucserel(str, start, i);    /* csere */
            permutal(str, start+1);
            betucserel(str, start, i);    /* visszacsere */
        }
    }
}
 
int main()
{
    char s[]="abcd";
    permutal(s, 0);
    printf("\n");
 
    return 0;
}

A fenti megoldás nem veszi figyelembe azt, ha egyforma betűk vannak a sztringben, és azokat is cseréli. Pl. az „abba” sztringnek többször is megjelennek ugyanazon permutációi. Ehhez a cserék előtt meg kell vizsgálnunk azt, hogy a cserélendő karakter 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(str, start+1);

for (i=start+1; i<hossz; ++i) {
   int k, kell_csere;

   kell_csere=1;
   for (k=start; k<i; ++k)           /* volt mar ez a betu? */
      if (str[k]==str[i])
         kell_csere=0;

   if (kell_csere) {
      betucserel(str, start, i);    /* csere */
      permutal(str, start+1);
      betucserel(str, start, i);    /* visszacsere */
   }
}

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. (Lehetne az első rekurzív hívás előtt is ellenőrizni.)

#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()
{
    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.

Ehhez azt kell észrevennünk, hogy a mennyit==0 báziskritérium jelenti azt, hogy megtaláltunk egy megoldást. Mire oda eljutunk a rekurzióban, már valamilyen érmekombinációval megoldottuk a feladatot. Ha útközben feljegyezzük az érmék számát egy segédtömbben, akkor ezen a ponton kiírva a tömb tartalmát, meg tudjuk adni a megoldásokat. (A második, harmadik báziskritérium olyan próbálkozást jelent, ami nem vezetett megoldásra.) A darab[] segédtömbben egy adott indexű elem azt tárolja, hogy az ugyanannyiadik indexű fajtak[] érméből mennyit adunk.

Kérdés még, hogy hol változik a tömb tartalma. A mennyit-fajtak[hanyadiktol] paraméterű rekurzív hívásnál próbálkozunk egy érme kiadásával. Ezért a rekurzív hívás előtt a megfelelő darabszámot megnöveljük eggyel (hogy a hívásban a darabszám tömb már megfelelő tartalmú legyen, és azt írjuk ki), és a hívás után pedig csökkentjük.

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

void penzvalto(int mennyit, int *fajtak, int hanyadiktol, int *darab)
{
    if (mennyit==0) {
        int i;
        
        for (i=0; fajtak[i]!=-1; ++i)
            if (darab[i]!=0)
                printf("%dx(%d Ft), ", darab[i], fajtak[i]);
        printf("\n");
        return;
    }

    if (mennyit<0 || fajtak[hanyadiktol]==-1)
        return;

    darab[hanyadiktol]++;
    penzvalto(mennyit-fajtak[hanyadiktol], fajtak, hanyadiktol, darab);
    darab[hanyadiktol]--;
    penzvalto(mennyit, fajtak, hanyadiktol+1, darab);
}

int main()
{
    int fajtak[]={5, 10, 20, 50, -1};
    int darab[]={0, 0, 0, 0};
    
    penzvalto(100, fajtak, 0, darab);
    
    return 0;
}

Írjunk először egy függvényt, amelyik egy sztringet kap paraméterként, és egy kezdő pozíciót. Térjen vissza a függvény azzal az indexszel, ahol először bezáró zárójelet talál. Ez könnyű, egyszerűen csak egy ciklust kell futtatnunk addig, amíg meg nem lesz a keresett karakter:

FÜGGVÉNY bezárót_keres(sztring, pozíció)
    AMÍG sztring[pozíció] != ')'
        pozíció=pozíció+1
    CIKLUS VÉGE

    VISSZA: pozíció
FÜGGVÉNY VÉGE

De ez még nem tudja a zárójelek egymásba ágyazását. Mit kell tenni, ha a bezárójel keresése közben egy nyitó zárójelet találunk? Akkor a következő bezárójel még nem az lesz, amit keresünk, hanem a mostani nyitónak a párja. Ez a belső zárójelpár közrefog egy sztringrészletet, amit át kéne ugranunk a keresés közben:

eredeti nyitó az elején          ezt a bezárót keressük
↓                                ↓
(A zárójelek (egymásba lehetnek) ) ágyazva.
             ↑                 ↑
             ezt a részt ki kell hagyni, mintha ott sem lenne

Hogy találjuk meg, hogy hol van ennek a nyitó zárójelnek a párja? Nagyon egyszerűen, hiszen már az előbb megírtuk azt a függvényt, ami ezt tudja! Ott van fent a pszeudokódja. Azt kiegészítve kapjuk a lenti függvényt. Az első utasítás a pozíció növelése; azzal az első nyitó zárójelet egyből átugorja.

FÜGGVÉNY bezárót_keres(sztring, pozíció)
    pozíció=pozíció+1
    CIKLUS AMÍG sztring[pozíció] != ')'
        FELTÉTEL HA sztring[pozíció] == '('
            pozíció = bezárót_keres(sztring, pozíció)
        FELTÉTEL VÉGE

        pozíció=pozíció+1
    CIKLUS VÉGE

    VISSZA: pozíció
FÜGGVÉNY VÉGE

#include <stdio.h>

/* Kap egy sztringet, es azon belul egy poziciot; ott egy nyito
   zarojelnek kell lennie. Annak a nyito zarojelnek megkeresi
   a bezaro parjat, es annak az indexet (poziciojat) adja vissza. */
int bezarot_keres(char *sztring, int pozicio)
{
    /* elso nyitot egybol atugorjuk */
    pozicio++;
    /* es keressuk a bezaro parjat */
    while (sztring[pozicio]!=')') {
        /* ha kozben nyitot talalunk, akkor azt a reszt,
           az azutan kovetkezo bezaroig, atugorjuk */
        if (sztring[pozicio]=='(')
            pozicio=bezarot_keres(sztring, pozicio);

        pozicio++;
    }

    return pozicio;
}

int main()
{
    char szoveg[]="(Ez egy (zarojeles) () sztring), aminek itt van vege a pontnal.";
    int pozicio=bezarot_keres(szoveg, 0);

    /* kiirjuk a keresett bezarotol kezdve */
    printf("%s\n", szoveg+pozicio);

    return 0;
}

Minden rekurzív problémának létezik iteratív megoldása. Ennek például nagyon egyszerű. Ha a keresés közben találunk egy nyitó zárójelet, akkor eggyel több bezáró zárójelig kell futtatni a keresést:

A (zárójelek (egymásba () lehetnek) ) ágyazva.
0011111111111222222222233222222222211000000000

#include <stdio.h>

/* Az elozo problema iterativ megoldasat adja ez a fuggveny. */
int bezarot_keres(char *sztring, int pozicio)
{
    /* most elvileg egy nyito zarojelen allunk;
     * vagyis egy bezaro zarojelet keresunk. */
    int hany_kell=1;

    while (hany_kell>0) {
        /* nezzuk a kovetkezo karaktert */
        pozicio++;
        if (sztring[pozicio]=='(')
            hany_kell++;
        if (sztring[pozicio]==')')
            hany_kell--;
    }

    return pozicio;
}

int main()
{
    char szoveg[]="(Ez egy (zarojeles) () sztring), aminek itt van vege a pontnal.";
    int pozicio=bezarot_keres(szoveg, 0);

    /* kiirjuk a keresett bezarotol kezdve */
    printf("%s\n", szoveg+pozicio);

    return 0;
}