**függvény**: van visszatérési értéke **eljárás**: nincs visszatérési értéke egy függvény **rekurzív**, ha önmagát hívja Rekurzív függvény felépítése: 1. **alapeset** (megállási feltétel): - ez az a feltétel, ami megállítja a rekurziót - ha nincs megállási feltétel, akkor a függvény végtelen sokszor hívja magát, emiatt általában elfogy a hívási verem (*call stack*) számára fenntartott memória és veremtúlcsordulási hibával (*stack overflow*) megszakad a program futása 2. **rekurzív eset** (a függvény önhívása): - a függvény önmagát hívja meg úgy, hogy a probléma egy „kisebb változatán” dolgozik - ezáltal fokozatosan közeledünk az alapesethez >[!example] Faktoriális > A matematikában egy $n$ nemnegatív egész szám **faktoriálisának** az $n$-nél kisebb vagy egyenlő pozitív egész számok szorzatát nevezzük. Jelölése: $n!$ . Megállapodás szerint: $0! = 1$. > > Pl. $5! = 5 * 4 * 3 * 2 * 1 = 120$. > > Pszeudo kódja: > ``` > Faktor(n) > If n = 0 return 1 > return n*Faktor(n-1) > ``` >[!note] **Feladat** >Készítsd el a Faktoriális probléma pszeudó kódjának Python-os implementációját. Az **oszd-meg-és-uralkodj** megközelítés lényege, hogy a feladatot több részfeladatra osztja, amelyek hasonlóak az eredeti feladathoz, de méretük kisebb, rekurzív módon megoldják a részfeladatokat, majd összevonják ezeket a megoldásokat, hogy az eredeti feladatra megoldást találjanak Az oszd-meg-és-uralkodj megközelítés a rekurzió minden szintjén az alábbi három lépésből áll: - **felosztja** a feladatot több részfeladatra - **uralkodik** a részfeladatokon rekurzív módon való megoldásukkal. Ha a részfeladatok mérete elég kicsi, akkor közvetlenül megoldja a részfeladatokat. - **összevonja** a részfeladatok megoldásait az eredeti feladat megoldásává >[!example] Hatványozás >A **hatványozás** két szám között értelmezett matematikai művelet. Jelölése $a^b$ (ejtsd: $a$ a $b$-ediken), ahol $a$-t **alap**nak, $b$-t **kitevő**nek nevezzük. > Nemnegatív egész $b$ kitevő esetén a hatványozás $b$ darab egymást követő azonos szám összeszorzását jelenti. Megállapodás szerint: $a^0=1$ Például: $6^{3}=6\cdot 6\cdot 6=216$. >``` >Hatvany(a, b) > If a == 0 and b = 0 return None > If b == 0 return 1 > return a * Hatvany(a, b-1) >``` >[!note] **Feladat** >Készítsd el a Hatványozás probléma pszeudó kódjának Python-os implementációját. >[!example] Fibonacci számok > Az első és második eleme $1$, a további elemeket az előző kettő összegeként kapjuk. > A Fibonacci számok végtelen, növekvő sorozatot alkotnak; ennek első néhány eleme a nulladiktól kezdve: $1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$ >``` >Fibonacci(n) > If n=1 or n=2 return 1 > return Fibonacci(n-1)+Fibonacci(n-2) >``` >[!note] **Feladat** >Készítsd el a Fibonacci számok probléma pszeudó kódjának Python-os implementációját. >[!example] Számjegyek összege > Pl.: 1234 → 1 + 2 + 3 + 4 = 10 >``` >SzamjegyOsszeg(n): > If n < 10 return n > return n % 10 + SzamjegyOsszeg(n // 10) >``` >[!note] **Feladat** >Készítsd el a Számjegyek összege probléma pszeudó kódjának Python-os implementációját. >[!example] Lista elemeinek összege > Pl.: `[9, 0, 7]` esetén az összeg `16`. >``` >ListaÖsszeg(L): > If hossz(L) = 0 return 0 > Else return L[0] + ListaOsszeg(L[1:]) >``` >[!note] **Feladat** >Készítsd el a Lista elemeinek összege probléma pszeudó kódjának Python-os implementációját. >[!example] Sztring megfordítása > Pl.: `abcde` esetén ez `edcba`. >``` >SztringFordit(s): > If hossz(s) = 0 return "" > Else return SztringFordit(s[1:]) + s[0] >``` >[!note] **Feladat** >Készítsd el a Sztring megfordítása probléma pszeudó kódjának Python-os implementációját. ## Feladatok >[!note] Visszaszámlálás. > **Feladat:** írj egy egyparaméteres rekurzív függvényt `visszamol(n)` néven, amely visszaszámol egyesével `n`-től `0`-ig! > > *Példa:* 5 → 5 4 3 2 1 0 >[!note] Szavak karakterenként >**Feladat:** írj egy egyparaméteres rekurzív függvényt `betuk(szo)` néven, amely szóközökkel elválasztva kiírja a `szo` betűit! > > *Példa:* alma → a l m a >[!note] Növekvő számok kiírása >**Feladat:** írj egy egyparaméteres rekurzív függvényt `sorozat(n)` néven, amely `1`-től `n`-ig kiírja a számokat egyesével növekvő sorrendben! > >*Példa:* 5 → 1 2 3 4 5 >[!note] Összeg intervallumban >**Feladat**: írj egy egyparaméteres rekurzív függvényt `osszeg(n)` néven, amely `1`-től `n`-ig összeadja a számokat! > >*Példa:* 4 → 10 >[!note] Számjegyek szorzata >**Feladat:** írj egy egyparaméteres rekurzív függvényt `szorzat(n)` néven, amely kiszámolja egy `n` egész szám számjegyeinek szorzatát! > >*Példa:* 26 → 12 >[!note] Karakter számlálása >**Feladat:** írj egy egyparaméteres rekurzív függvényt `karakterszamlalo(szoveg)` néven, amely megszámolja hány `a` betű van a szövegben! > >*Példa:* alma → 2 ## Források - https://hu.wikipedia.org/wiki/Rekurzi%C3%B3 (utolsó hozzáférés dátuma: 2025. 09. 11.) - https://hu.wikipedia.org/wiki/Faktori%C3%A1lis (utolsó hozzáférés dátuma: 2025. 09. 11.) - https://hu.wikipedia.org/wiki/Hatv%C3%A1ny (utolsó hozzáférés dátuma: 2025. 09. 11.)