Rekurzíó

Rekurzív függvények

Azt mondjuk, hogy egy függvény rekurzív ha meghívja önmagát (közvetlenül vagy más függvényhívásokon keresztül).

Példa:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
using namespace std;

int f(int n)
{
    if (n == 0)
        return 1;

    int eredmeny = n * f(n-1);
    return eredmeny;
}

int main()
{
    int n;
    cin >> n;

    cout << f(n) << endl;

    return 0;
}

Az f függvény a paraméterként megadott természetes szám faktoriálisát számítja ki rekurzívan.

Példa: egy természetes szám számjegyeinek összege rekurzívan.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <iostream>
using namespace std;

int szjossz(int n)
{
    if (n == 0)
        return 0;

    return n%10 + szjossz(n/10);
}

int main()
{
    cout << szjossz(125) << endl;

    return 0;
}

Példa: egy tömb elemeinek összege rekurzívan.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
using namespace std;

int osszeg(int n, int t[])
{
    if (n == 0)
        return 0;

    return osszeg(n-1, t) + t[n-1];
}

int main()
{
    int n = 3;
    int t[] = {10,20,30};

    cout << osszeg(n, t) << endl;

    return 0;
}

Feladat:

Számítsuk ki adott a pozitív egész és b természetes szám esetén az a szám b-edik hatványát minél kevesebb szorzással!

Ötlet: “Gyors hatványozás” - minden lépésben felezzük a kitevőt.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int hatvany(int a, int b)
{
    if (b == 0) return 1;
    if (b == 1) return a;

    int fel = hatvany(a, b/2);

    if (b % 2 == 0)
        return fel*fel;
    else
        return fel*fel*a;
}

Házi feladat

Teszteljük az előző függvényt és írjunk rekurzív függvényt az alábbiak meghatározására:

  1. egy szám számjegyeinek száma
  2. egy szám legkisebb számjegye
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int hanyszj(int n)
{
    if (n < 10)
        return 1;

    return 1 + hanyszj(n/10);
}

int minszj(int n)
{
    if (n < 10)
        return n;

    int eddigi = minszj(n/10);
    int utolso = n%10;

    if (eddigi < utolso)
        return eddigi;
    else
        return utolso;
}