Labor, 8. hét: rekurzió

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

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=40-re! Mit tapasztalsz? (Ötlet: figyeld meg az előző előadás ide vonatkozó diáját.)

Kövesd 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) {
    int i;
    for (i = 0; i < 40; i++)
        printf("%d\n", fib(i));

    return 0;
}

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

Megoldás

#include <stdio.h>

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;
}

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

  • ak=(a2)k/2, ha k páros, és
  • 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!

Megoldás

#include<stdio.h>

double hatvany(double alap, unsigned kitevo) {
    /* barminek a 0. 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) {
    int i;
    for (i = 0; i < 16; ++i)
        printf("%d %g\n", i, hatvany(2, i));

    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 az előbbi 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 (36os számrendszerig) */
void atvalt2(int n, int r) {
    char *t = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    /* 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 (a határok ellenőrzésétől most eltekintek) */
    putchar(t[n % r]);
}

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 több mint 3 számjegyű */
    if (n / 1000 > 0) {
        /* Levágunk 3 számjegyet (osztás 1000-el), és erre hívjuk a függvényt */
        kiir(n / 1000);
        /* Kiírjuk a levágott 3 számjegyet vezető 0-kkal */
        printf(" %03d", n % 1000);
    }
    else
        printf("%d", n);      /* Különben simán kiírjuk a számot */
}

int main(void) {
    kiir(16077216);

    return 0;
}

6. További feladatok

Írd meg a fenti függvények iteratív párját! Melyik algoritmust könnyű iteratívan megírni? Melyiket nem?

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