Labor, 6. hét: rekurzió
Czirkos Zoltán, Pohl László · 2025.10.10.
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:
- A rekurzióról szóló előadás átismétlése.
A Fibonacci-sorozat elemeit a következő egyszerű algoritmus adja:
F0 = 0F1 = 1Fn = 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.
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;
}Í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.
Í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ó.