recursion (tsz. recursions)

1. (informatika) rekurzió

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ó.

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.

#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).

A faktoriális egy klasszikus példa a rekurzióra: $${\displaystyle 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.

A Fibonacci-sorozat: $${\displaystyle F(n)=F(n-1)+F(n-2)}$$ Alapfeltételek: $${\displaystyle F(0)=0,\quad 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.

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 != -1) return memo; // Ha már kiszámoltuk, ne számoljuk újra
    return memo = 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.

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

#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 == keresett) return kozep;
    else if (tomb > 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);
    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.

✅ 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

❌ 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

• 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.

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.

• recursion - Szótár.net (en-hu)
• recursion - Sztaki (en-hu)
• recursion - Merriam–Webster
• recursion - Cambridge
• recursion - WordNet
• recursion - Яндекс (en-ru)
• recursion - Google (en-hu)
• recursion - Wikidata
• recursion - Wikipédia (angol)