Recursivitate

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

Exemple:

• factorialul unui număr: \( N! = N \cdot (N-1)! \);
• ridicarea la putere: \( a^n = a \cdot a^{n-1} \);
• termenul unei progresii aritmetice: \( a_n = a_{n-1} + r \);
• șirul lui Fibonacci: \( F_n = F_{n-1} + F_{n-2} \);
• etc.

Să observăm că aceste reguli nu se aplică întotdeauna. Dacă ar fi așa, pentru \( 3! \) am obține:

\(3! = 3 \cdot 2!\), \(2! = 2 \cdot 1!\), \(1! = 1 \cdot 0!\), \(0! = 0 \cdot (-1)!\)

De aici am putea deduce că \( 0! = 0\) și înlocuind în relațiile de mai sus obținem că \( n! = 0\), pentru orice număr natural \( n \). Bineînțeles, nu este corect. De fapt, formula recursivă pentru \( n! \) se aplică numai pentru \( n > 0 \), iar prin definiție \( 0! = 1\) .

Astfel, identificăm următoarea definiție pentru \( n! \), acum completă: \( n! = \begin{cases}
1& \text{dacă } n = 0,\\
n \cdot (n-1)!& \text{dacă } n > 0.
\end{cases} \)

Similar, pentru toate formulele de mai sus exista cel puțin o situație în care formula recursivă nu se mai poate aplica, iar rezultatul se determină în mod direct.

Î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 C++

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);
}

Cum funcționează recursivitatea?

Ne amintim că toate variabilele locale din definiția unei funcții precum și valorile parametrilor formali se memorează la apel în memoria de tip STIVĂ (STACK).

Pentru fiecare apel al unei funcții se adaugă pe stivă o zonă de memorie în care se memorează variabilele locale și parametrii pentru apelul curent. Această zonă a stivei va exista până la finalul apelului, după care se va elibera. Dacă din apelul curent se face un alt apel, se adaugă pe stivă o nouă zonă de memorie, iar conținutul zonei anterioare este inaccesibil până la finalul acelui apel. Aceste operații se fac la fel și dacă al doilea apel este un autoapel al unei funcții recursive.

Să considerăm acum următoarea secvență:

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

int main(){
    int x = fact(3);
    cout << x;
    return 0;
}

Să urmărim pas cu pas execuția acestui program:

int x = 

x = ??

fact(3) 

Zona 1: n = 3, f = 3 *  fact(2) = ??

Zona 0: x = ??

fact(2) 

Zona 2: n = 2, f = 2 *  fact(1) = ??

Zona 1: n = 3, f = 3 *  fact(2) = ??

Zona 0: x = ??

fact(1) 

Zona 3: n = 1, f = 2 *  fact(0) = ??

Zona 2: n = 2, f = 2 *  fact(1) = ??

Zona 1: n = 3, f = 3 *  fact(2) = ??

Zona 0: x = ??

fact(0) 

Zona 4: n = 0, f = 1

Zona 3: n = 1, f = 2 *  fact(0) = ??

Zona 2: n = 2, f = 2 *  fact(1) = ??

Zona 1: n = 3, f = 3 *  fact(2) = ??

Zona 0: x = ??

fact(1) 

Zona 3: n = 1, f = 1 *  1 = 1

Zona 2: n = 2, f = 2 *  fact(1) = ??

Zona 1: n = 3, f = 3 *  fact(2) = ??

Zona 0: x = ??

fact(2) 

Zona 2: n = 2, f = 2 *  1 = 2

Zona 1: n = 3, f = 3 *  fact(2) = ??

Zona 0: x = ??

fact(3) 

Zona 1: n = 3, f = 3 * 2 = 6

Zona 0: x = ??

cout << x; 
return 0;

Zona 0: x = 6

Observații: La fiecare apel al funcției fact avem variabilele n și f. Ele însă sunt variabile diferite, cu valori diferite, memorate în zone diferite ale stivei. La un moment dat, se pot folosi numai variabilele din zona de memorie curentă, cea din “vârful” stivei.

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:

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;
}

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;
}

Alte formule recursive

• calculul combinărilor: \( {n \choose k} = \begin{cases}
  1& \text{dacă } n = k \text{ sau } k = 0,\\
  { {n-1} \choose {k-1} } + { {n-1} \choose k } & \text{altfel}.
  \end{cases} \), unde \( n \choose k \) înseamnă “combinări de n luate câte k”

• calculul combinărilor: \( {n \choose k} = \begin{cases}
  1& \text{dacă } k = 0,\\
  \frac{n – k + 1}{k} \cdot { n \choose {k-1} } & \text{altfel}.
  \end{cases} \)

• cel mai mare divizor comun a două numere: \( cmmdc(a,b) = \begin{cases}
  a& \text{dacă } b = 0,\\
  cmmdc(b , a \% b) & \text{dacă } b > 0.
  \end{cases} \)

• operații cu cifrele unui număr natural, de exemplu:
  • suma cifrelor: \( sumcif(n) = \begin{cases}
    n& \text{dacă } n < 10,\\
    n \% 10 + sumcif(n/10) & \text{dacă } n \geqslant 10.
    \end{cases} \)
  • numărul de cifre: \( nrcif(n) = \begin{cases}
    1& \text{dacă } n < 10,\\
    1 + nrcif(n/10) & \text{dacă } n \geqslant 10.
    \end{cases} \)
  • cifra maximă: \( cifmax(n) = \begin{cases}
    n& \text{dacă } n < 10,\\
    max(n \% 10 , cifmax(n/10)) & \text{dacă } n \geqslant 10.
    \end{cases} \)

Tipuri de recusivitate

• recursivitate directă: în definiția funcției F apare apelul funcției F;
• recursivitate indirectă: în definiția funcției F apare apelul funcției G, iar în definiția funcției G apare apelul lui F.

Fun

Dacă v-a plăcut imaginea de mai sus, căutați pe net droste effect