Recursion

1. Sablon:Enmatek rekurzió
2. önhívás
3. önhivatkozás

Rekurzió C++-ban – Részletes Magyarázat

A rekurzió egy olyan programozási technika, amelyben egy függvény önmagát hívja meg. Ez gyakran hasznos összetett problémák megoldására, különösen akkor, ha a probléma kisebb, hasonló részekre bontható.

---

1. A rekurzió működése

A rekurzió alapvetően két fő részből áll: - Báziseset (alapeset): Egy olyan feltétel, amelynél a függvény már nem hívja meg önmagát, hanem közvetlenül visszatér egy értékkel. Ez megakadályozza a végtelen rekurziót. - Rekurzív eset: A függvény önmagát hívja meg egy kisebb méretű bemenettel.

Egyszerű példa – Számlálás visszafelé

#include <iostream>

void szamlalas(int n) {
    if (n == 0) { // Báziseset
        std::cout << "Start!" << std::endl;
        return;
    }
    std::cout << n << std::endl;
    szamlalas(n - 1); // Rekurzív hívás
}

int main() {
    szamlalas(5);
    return 0;
}

Kimenet:

5
4
3
2
1
Start!

Ebben a példában a függvény mindig n-1 értékkel hívja meg önmagát, amíg n el nem éri a 0-t (báziseset).

---

2. Faktoriális számítás rekurzióval

A faktoriális egy klasszikus példa a rekurzióra: $$n!=n\times (n-1)!$$ A C++ megvalósítás így néz ki:

#include <iostream>

long long faktorialis(int n) {
    if (n == 0) return 1; // Báziseset
    return n * faktorialis(n - 1); // Rekurzív eset
}

int main() {
    int szam = 5;
    std::cout << szam << "! = " << faktorialis(szam) << std::endl;
    return 0;
}

Kimenet:

5! = 120

Itt a függvény addig hívja meg önmagát, amíg n el nem éri a 0-t, majd az értékek visszaadódnak az eredeti hívásig.

---

3. Fibonacci-számok kiszámítása rekurzióval

A Fibonacci-sorozat: $$F(n)=F(n-1)+F(n-2)$$ Alapfeltételek: $$F(0)=0,F(1)=1$$

C++ kód:

#include <iostream>

int fibonacci(int n) {
    if (n <= 1) return n; // Báziseset
    return fibonacci(n - 1) + fibonacci(n - 2); // Rekurzív eset
}

int main() {
    int n = 10;
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

Kimenet:

Fibonacci(10) = 55

Probléma: Ez az algoritmus exponenciális időben fut ((O(2^n))), mivel minden hívás két újabb rekurzív hívást indít el.

Optimalizált megoldás: Memorizáció (dinamikus programozás)

Az ismételt számítások elkerülése érdekében tárolhatjuk az eredményeket egy tömbben:

#include <iostream>
#include <vector>

std::vector<int> memo(100, -1);

int fibonacci_mem(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n]; // Ha már kiszámoltuk, ne számoljuk újra
    return memo[n] = fibonacci_mem(n - 1) + fibonacci_mem(n - 2);
}

int main() {
    int n = 10;
    std::cout << "Fibonacci(" << n << ") = " << fibonacci_mem(n) << std::endl;
    return 0;
}

Időkomplexitás: (O(n)), mivel minden Fibonacci-értéket csak egyszer számítunk ki.

---

4. Bináris keresés rekurzióval

A bináris keresés egy hatékony algoritmus rendezett tömbben való keresésre Értelmezés sikertelen (formai hiba): {\displaystyle \(O(\log n)\)} .

C++ kód:

#include <iostream>

int binaris_kereses(int tomb[], int bal, int jobb, int keresett) {
    if (bal > jobb) return -1; // Nem található
    int kozep = bal + (jobb - bal) / 2;
    
    if (tomb[kozep] == keresett) return kozep;
    else if (tomb[kozep] > keresett) return binaris_kereses(tomb, bal, kozep - 1, keresett);
    else return binaris_kereses(tomb, kozep + 1, jobb, keresett);
}

int main() {
    int tomb[] = {2, 3, 4, 10, 40};
    int meret = sizeof(tomb) / sizeof(tomb[0]);
    int keresett = 10;
    
    int eredmeny = binaris_kereses(tomb, 0, meret - 1, keresett);
    
    if (eredmeny != -1)
        std::cout << "Az elem indexe: " << eredmeny << std::endl;
    else
        std::cout << "Elem nem található" << std::endl;
    
    return 0;
}

Kimenet:

Az elem indexe: 3

Ez az algoritmus mindig a tömb középső elemével hasonlítja össze a keresett értéket, és szükség szerint a bal vagy jobb részhalmazra szűkíti a keresést.

---

5. Rekurzió előnyei és hátrányai

Előnyök:

✅ Egyszerűbb, olvashatóbb kód rekurzív problémákra
✅ Természetes módon használható fák, gráfok bejárására
✅ Bizonyos problémákhoz tisztább megoldás, mint a ciklusok

Hátrányok:

❌ Magas memóriahasználat (minden függvényhívás új példányt hoz létre a veremben)
❌ Rosszabb teljesítmény, ha nem optimalizálják (például Fibonacci esetén)
❌ Könnyű végtelen ciklusba kerülni, ha nincs megfelelő báziseset

---

6. Mikor érdemes rekurziót használni?

• Fa- és gráfalgoritmusokhoz (pl. mélységi keresés - DFS)
• Matematikai problémákhoz, mint a faktoriális vagy Fibonacci-sorozat
• Backtracking algoritmusokhoz, mint például a királynők problémája vagy a labirintuskeresés
• Ha a probléma természetesen rekurzív, és a kód így érthetőbb lesz

Ha a teljesítmény kritikus, érdemes iteratív megoldásokat vagy optimalizációkat alkalmazni.

---

Összegzés

A rekurzió egy erőteljes eszköz C++-ban, amely lehetővé teszi az önmagát hívó függvények használatát összetett problémák egyszerűbb megoldására. Bár elegáns, körültekintően kell alkalmazni, hogy elkerüljük a nagy memóriafelhasználást és a teljesítményproblémákat.