Recursivitate

Recursivitatea reprezintă proprietatea unor noțiuni de a se defini prin ele însele. Câteva exemple pot fi:

• șirul lui Fibonacci: Fn = Fn−1 + Fn-2
• factorialul unui număr: n! = n ⋅ (n - 1)!
• progresiile aritmetice: An! = An-1 + r

În C++, recursivitatea se poate realiza apelând funcții care se pot autoapela. Primul apel realizat, se numește apel principal.

Cum funcționează

Variabilele locale, precum și valorile parametrilor se memorează la fiecare apel și sunt specifice instanței respective a apelului funcției. Acestea sunt memorate în memoria de tip stivă.

Pentru fiecare apel al funcției, se va adăuga în stivă o zonă de memorie dedicată apelului respectiv, în care sunt stocate toate variabilele locale și parametrii cu care a fost făcut apelul. Această zonă va persista până când funția va fi fost încheiată, moment în care memoria dedicată apelului se va elibera. Dacă din apelul curent se efectuează alt apel, pe stivă se va adăuga o nouă zonă de memorie, iar procesul se repetă. Accesibilă va fi doar acea bucată de memorie care se află vârful stivei, aceasta reprezentând chiar ultimul apel al funcției.

Apelul se va termina atunci când return este atins sau când funția ajunge la final. După aceea, se va continua rularea apelului anterior, de unde a fost lăsat. Valorile variabilelor vor fi în continuare cele specifice numai acestui apel.

Anatomia unei funcții recursive

Pentru a putea utiliza o funcție recursiva avem nevoie de mai multe elemente. Acestea sunt definiția funției, la care se adaugă condiția de oprire, alte operații și autoapelarea și apelarea principală.

Sintaxă

int FunctieRecursiva(int n) {
    if (conditie_de_oprire) {
        return valoare_default;
    }

    alte_operatii();

    FunctieRecursiva(NoulN(n));
}

int main() {
    ...

    FunctieRecursiva(valoare);

    ...
}

Factorialul unui număr

De exemplu, factorialul unui număr se poate calcula așa:

Varianta iterativă

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

    return p;
}

Varianta recursivă

int Factorial(int n){
    if(n == 0) {
        return 1;
    }

    return n * Factorial(n - 1);
}

Se poate observa clar condiția de oprire a funcției recursive, anume daca n este 0, returnează 1. Aceasta se datorează definiției matematice a funcției recursive, care spune că 0! = 1.

Șirul lui Fibonacci

Un alt exemplu este șirul lui Fibonacci.

Varianta recursivă

int Fibonacci(int n){
    if(n == 0) {
        return 0;
    }
    else if (n == 1) {
        return 1;
    }
    
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Rezolvarea problemelor

Pentru a putea rezolva probleme utilizând metode recursive, se pot scrie toți pașii, în ordinea în care îi rulează programul, tinând cont si actualizând valorile variabilelor și ce returnează fiecare apel în parte. Cu timpul, exersând, vă veți obișnui cu recursivitatea și vă va fi mult mai ușor.

Acestea sunt câteva formule simple de recursivitate:

• factorialul unui număr: 1, daca n = 0 SAU n! = n * (n - 1)!, altfel
• calculul combinărilor: (n, k) = 1, daca n = k sau k = 0 SAU (n - 1, k - 1) + (n - 1, k), altfel, unde (n, k) reprezintă combinări de n luate câte k.
  
  

Generarea submulțimilor

Se dă un număr natural n. Să se genereze toate submulțimile mulțimii {1,2,3,...,n}.

#include <iostream>
using namespace std;

int x[15];
int n;

void Print(int k){
    for(int i = 1 ; i <= k ; i++) {
        cout << x[i] << " ";
    } 
    cout << '\n';
}

void BKT(int k){
    for(int i = x[k - 1] + 1; i <= n; i++) {
        x[k] = i;
        Print(k);

        BKT(k + 1);
    }
}

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

    return 0;
}

Generarea permutărilor

Fie un număr natural n. Să se afișeze, în ordine lexicografică, permutările mulțimii {1,2,⋯,n}.

#include <iostream>
using namespace std;

int x[15];
int n;

void Print() {
    for (int i = 1; i <= n; i++) {
        cout << x[i] << " ";
    }
    cout << '\n';
}

// Checks if elements are repeating
bool IsValid(int k) {
    for(int i = 1; i < k; i++) {
        if(x[k] == x[i]) {
            return false;
        }
    }

    return true;
}

void BKT(int k) {
    for(int i = 1; i <= n ; i++) {
        x[k] = i;

        if(IsValid(k)) {
            if(k == n) {
                Print();
            }
            else {
                BKT(k + 1);
            }
        }    
    }
}

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

    return 0;
}

Probleme

Submultimi | SubmDiv | Permutari | Combinari | cifre_c | Aranjamente | numere124 | FiboRec | DivImpRec | FactorialRec | FactorialRec1 | VectorMaxMinSumRec