9. labor: Rekurzió

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.

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) {
    if (n==0) return 0;  /* 0. elem a 0    <-- ezek a rekurzió */
    if (n==1) return 1;  /* 1. elem az 1   <-- leállító feltételei */

    return fib(n-1) + fib(n-2);  /* n-edik elem az előző kettő összege */
}

int main() {
    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 elemű, egész értékekkel feltöltött tömböt. Hívd meg mind a négy függvényt a tömbre!

Megoldás

#include <stdio.h>

void tomb_kiir_elore(int t[],int n) {
    if(n>0) {                     /* Ha van benne elem */
        printf("%d\n",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 (pointer aritmetika) é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, csak egyel kisebb darabszámra */
        printf("%d\n",t[0]);      /* Kiírjuk az első elemet */
    }
}

int main() {
    int t[]={1,2,3,4,5};
    
    tomb_kiir_elore(t,5);
    printf("\n\n\n");
    tomb_kiir_hatra(t,5);
    
    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:

Í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()
{
    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 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(){
    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()
{
    kiir(16077216);

    return 0;
}

6 További feladatok

Rekurzió

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

Javított buborékrendezés

A buborékrendezés egymás melletti elemeket cserél sorban. Egy sor csere hatására a legnagyobb elem a tömb végére vándorol; a következő körben azt már nem kell vizsgálni, hanem a tömb eggyel rövidebb részletét csak. Ezt kell folytatni addig, amíg el nem fogy a tömb.

A buborékrendezés hatékonysága javítható azzal, ha megjegyezzük, hogy a vizsgált tömbrészletnél volt-e csere. Ha nem volt, akkor minden pár jó sorrendben van. Akkor a rövidebb részt vizsgálva is ugyanerre az eredményre jutnánk, vagyis a külső ciklust már nem kell folytatni. Implementáld ezt a változatot!

Megoldás

void buborek(double t[], int db)
{
   int i, j;
   int voltcsere=1;
   /* egyre rövidebb tömbrészletek ciklusa */
   for (i=db-1; i>0 && voltcsere; --i){
        voltcsere=0;
        /* egymás utáni párok ciklusa */
        for (j=0; j<i; ++j){
            if (t[j+1]<t[j]) {       /*  összehasonlítás */
                double temp=t[j];
                t[j]=t[j+1];          /*  csere */
                t[j+1]=temp;
                voltcsere=1;
            }
        }
    }
}