Funcțiile recursive

Recursivitatea reprezintă proprietatea unor noțiuni de a se defini prin ele însele.

În C++, recursivitatea se realizează prin intermediul funcțiilor, care se pot autoapela. Ne amintim că o funcție trebuie definită iar apoi se poate apela. Recursivitatea constă în faptul că în definiția unei funcție apare apelul ei însăși. Acest apel, care apare în însăși definiția funcției, se numește autoapel. Primul apel, făcut în altă funcție, se numește apel principal.

Exemplu:

Să scriem o funcție C++ care returnează factorialul unui număr natural transmis ca parametru. Varianta nerecursivă (iterativă) este următoarea:

int fact(int n)
{
    int p = 1;
    for(int i = 1 ; i <= n ; i ++)
        p = p * i;
    return p;
}

Să observăm că această funcție determină rezultatul corect pentru valori ale lui n mai mari sau egale cu 0 (valori mici, practic n <= 12). Funcția determină corect rezultatul și pentru n == 0.

O variantă recursivă pentru determinarea lui n!, care folosește observațiile de mai sus, este:

int fact(int n)
{
    if(n == 0)
        return 1;
    else
        return n * fact(n-1);
}

Observații:

• este obligatoriu ca în definiția unei funcții recursive să apară cazul particular (în care să nu aibă loc autoapelul). În caz contrar autoapelurile vor avea loc "la nesfârșit". De fapt, în urma prea multor autoapeluri, stiva se va ocupa în totalitate și execuția programului se va întrerupe.
• este obligatoriu ca, pentru cazurile neelementare, valorile la autoapel a parametrilor să se apropie de valorile din cazul elementar. Altfel se va întâmpla situația descrisă mai sus: stiva se va ocupa în totalitate și programul se va opri, fără a determina/afișa rezultatele dorite :).

Cum facem autoapelul?

Autoapelul se face în conformitate cu antetul funcției recursive. Astfel:

• dacă funcția recursivă este de tip non-void, autoapelul se va face într-o expresie;
• dacă funcția recursivă este de tip void, autoapelul se va face într-o instrucțiune de sine stătătoare; dacă funcția întoarce valori, se vor folosi parametri de ieșire.

Exemple:

Funcție de tip void

void fact(int n, int &r)
{
    if(n == 0)
        r = 1;
    else{
        fact(n - 1 , r);
        r = r * n;
    }
}
int main()
{
    int a;
    fact(4, a);
    cout << a;
    return 0;
}

Funcție de tip non-void

int fact(int n)
{
    int r;
    if(n == 0)
        r = 1;
    else
        r = n * fact(n - 1);
    return r;
}
int main()
{
    int a;
    a = fact(4);
    cout << a;
    return 0;
}