Labor, 9. hét: rekurzió

Czirkos Zoltán, Pohl László · 2023.10.27.

Rekurzió vizsgálata nyomkövetővel. Rekurzív algoritmusok írása: báziskritérium és egyszerűsítések.

A feladatok nagy része a rekurzió témakörét dolgozza fel. Itt fontos az, hogy a nyomkövetővel mindenki megvizsgálja a rekurzió működését, különösen a Fibonacci számokat kiszámoló programnál. A tömb előre-hátra feladatokhoz az előadás sztringes példája adhat ötletet. Ennek kidolgozása pedig rávezet a számrendszer váltó feladat megoldására.

Felkészülés a laborra:

1. Fibonacci

A Fibonacci-sorozat elemeit a következő egyszerű algoritmus adja:

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2

Írj rekurzív függvényt, amely kiszámítja ennek n-edik elemét! Próbáld ki a függvényt n=45-re! Mit tapasztalsz? (Ötlet: figyeld meg az előadás ide vonatkozó diáját.)

Kövesd a függvény működését a fejlesztőkörnyezet nyomkövetőjében (debugger)! Indítsd el a programot, és figyeld a működést n=5 esetén. Esetleg használhatsz a programba írt nyomkövetést is: pl. minden fib() függvényhívás esetén írja ki a függvény a paraméterként kapott n értéket.

Megoldás
#include <stdio.h>

/* Fibonacci sorozat */
int fib(int n) {
    /* báziskritériumok */
    if (n == 0) return 0; /* 0. elem a 0 */
    if (n == 1) return 1; /* 1. elem az 1 */

    /* egyszerűsítés */
    return fib(n - 1) + fib(n - 2); /* n-edik elem az előző kettő összege */
}

int main(void) {
    for (int i = 0; i < 45; i++)
        printf("%d\n", fib(i));

    return 0;
}

2. Szöveg kiírása

Próbáld ki az alábbi két programot! Mi a különbség az alábbi két függvény között? Mi a különbség a futási eredményben?

#include <stdio.h>

void sztringet_kiir_1(char *szoveg) {
    if (szoveg[0] == '\0')
        return;
    putchar(szoveg[0]);
    printf("%s", szoveg + 1);     // !
}


void sztringet_kiir_2(char *szoveg) {
    if (szoveg[0] == '\0')
        return;
    putchar(szoveg[0]);
    sztringet_kiir_2(szoveg + 1); // !
}


int main(void) {
    sztringet_kiir_1("alma");
    sztringet_kiir_2("alma");
    
    return 0;
}
Megoldás

A futási eredményben semmi. Mindkettő ugyanazt a feladatot oldja meg. A gondolatmenetük: a sztring kiírásához ki kell írni a sztring első karakterét, utána pedig a sztring fennmaradó részét. Például alma = a+lma. Az előbbi függvény a fennmaradó részt printf-fel írja ki, az utóbbi rekurzívan. Rekurzívan pedig, lma = l+ma, és így tovább, amíg el nem fogy a sztring.

3. Tömb előre és hátra

Írj a) iteratív b) rekurzív függvényt, amely kiírja egy tömb elemeit x) előrefelé y) hátrafelé. Vegye át mindegyik függvény paraméterként a kiírandó tömböt és annak méretét! Hozz létre a főprogramban egy tíz és egy öt elemű, egész értékekkel feltöltött tömböt. Hívd meg a függvényeket a tömbökre!

Figyeld meg, pontosan mit kér a feladat: összesen négy, egymástól független függvényt kell írnod, hogy a két feladatot két-két verzióban megoldd.

Megoldás
#include <stdio.h>

/*Az iteratív függvények triviálisak*/

void tomb_kiir_elore(int t[], int n) {
    if(n > 0) {                    /* Ha van benne elem */
        printf("%d ", t[0]);       /* Kiírjuk az első elemet */
        tomb_kiir_elore(t+1, n-1); /* Meghívjuk ugyanezt a függvényt, csak a tömb következő */
                                   /* elemétől kezdve és eggyel kisebb mérettel */
    }
}

void tomb_kiir_hatra(int t[], int n) {
    if(n > 0) {                    /* Ha van benne elem */
        tomb_kiir_hatra(t+1, n-1); /* Meghívjuk ezt a függvényt, egyel kisebb méret */
        printf("%d ", t[0]);       /* Kiírjuk az első elemet */
    }
}

int main(void) {
    int t5[] = {1,2,3,4,5}, t10[] = {1,2,3,4,5,6,7,8,9,10};
    
    tomb_kiir_elore(t5, 5); printf("\n");
    tomb_kiir_hatra(t5, 5); printf("\n");
    tomb_kiir_elore(t10, 10); printf("\n");
    tomb_kiir_hatra(t10, 10); printf("\n");
    
    return 0;
}

4. 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! 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ó.

Megoldás
#include <stdio.h>

/* Ez a függvény r<=10 számrendszerekre működik */
void atvalt(int n, int r) {
    /* Ha n nem osztható az alapszámmal, akkor rekurzívan meghívjuk a függvényt */
    if (n / r > 0)
        atvalt(n / r, r);
    /* Majd kiírjuk a maradékot */
    printf("%d", n % r);
}

/* Ez a teljes angol ABC-t fel tudja használni (36-os számrendszerig) */
void atvalt2(int n, int r) {
    /* Ha n osztható az alapszámmal, akkor rekurzívan meghívjuk a függvényt */
    if (n / r > 0)
        atvalt2(n / r, r);
    /* Majd kiírjuk a maradékot */
    if (n % r < 10)
        printf("%c", n % r + '0');
    else
        printf("%c", n % r - 10 + 'A');
}

int main(void) {
    atvalt(27, 5);  /* 102 */
    printf("\n");
    atvalt(13, 2);  /* 1101 */
    printf("\n");
    atvalt2(64519, 16);  /* FC07 */

    return 0;
}

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

Megoldás
#include <stdio.h>

void kiir(int n) {
    /* ha nincs 3 számjegyű, simán kiírjuk, nincs több teendő */
    if (n < 1000) {
        printf("%d", n);
        return;
    }
    
    /* amúgy alsó 3 számjegyet eldobva, előbb kiírjuk az elejét. */
    /* utána pedig az alsó 3 számjegyet, vezető nullákal */
    kiir(n / 1000);
    printf(" %03d", n % 1000);
}

int main(void) {
    kiir(16077216);

    return 0;
}

6. További feladatok

Ha elkészültél, oldd meg az emeletes házas feladatot a feladatgyűjteményből!