Ce este recursivitatea?

Recursivitatea reprezinta proprietatea unor notiuni de a se defini prin ele insele. Cateva exemple:

• sirul lui Fibonacci: F_N = F_N-1 + F_N-2;
• ridicarea la putere: aⁿ = a * a^n-1;
• factorialul unui numar: N! = N * (N – 1)!

Cu alte cuvinte – functia este recursiva, daca definitia ei foloseste o referire la ea insasi.

Exemplu – cautarea fisierelor

Sa ne imaginam urmatoarea problema: dorim sa cautam in calculator toate fisierele ce contin literele “TPN”.

Daca ar trebuii sa numeri fisierele “TPN” doar din My Computer, totul ar fi foarte simplu, insa problema intervine in momentul cand dam de foldere. Deoarece acestea contin la randul lor sub-foldere s.a.m.d.

Aceasta functie primeste ca si parametru un folder. Daca folderul este gol, atunci functia se opreste, in caz contrar, continua. Ne luam o variabila suma si dupa care numaram cate fisiere cu TPN avem, destul de simplu. Insa partea interesanta vine din for-ul care parcurge foldere, deoarece in acesta ne intalnim cu functia recursiva. Am sa las mai jos un grafic cum ruleaza algoritmul pe exemplul nostru.

Fiecare functie recursiva trebuie sa aiba un punct in care sa se opreasca (pt ca altfel s-ar apela la infinit). In cazul nostru, functia se opreste in momentul in care folderul nu mai contine alte sub-foldere.

Exemplu – Sirul lui Fibonacci

In caz ca nu stii ce e aia, citeste mai intai articolul nostru: Sirul lui Fibonacci in C++. Numerele Fibonacci.

Sirul lui Fibonacci este cel mai usor exemplu atunci cand vine vorba despre recursiune. De multe ori spunem ca acest sir este definit recursiv.

Cu totii stim ca F_n = F_n-1 + F_n-2 dar acest lucru nu este suficient pentru a oprii recursivitatea. Am mentionat si mai sus ca ne trebuie un punct in care sa oprim recursiunea. In cazul sirului lui Fibonacci acest punct de oprire este definit prin primii 2 termeni ai sirului: F₀ = 0 si F₁ = 1.

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

Probabil va intrebati de ce e asa scurt codul, varianta mai lunga era: Sirul lui Fibonacci – varianta lunga. Insa am zis sa il prescurtez pentru usurinta.

Haideti sa calculam impreuna Fib(4) – si sa facem cateva observatii.

Putem observa ca acest algoritm a generat un arbore binar foarte chipes. In general, orice functie recursiva va genera mai mult sau mai putin o figura de genul. Frunzele oricarui arbore generat de o functie recursiva vor fi conditiile de oprire.

Un lucru pe care il putem observa este ca noi calculam Fib(2) de doua ori – asadar aceasta abordare nu este suficienta pentru a-l face eficient. Aceasta problema se rezolva printr-o tehnica in programarea dinamica numita memorizare. (nu se cere la clasa, nu va faceti griji)

De asemenea mai exista o teorema care spune: orice functie implementata recursiv poate fi definita printr-o functie implementata iterativ (de exemplu algoritmul de mai sus devenea):

int Fib(int n) {
    if(n == 0)
        return 0;
    if(n == 1)
        return 1;
    if(n == 2)
        return 1;

    int nr_2, nr_1 = 1, nr_0 = 1;
    for(int i = 3; i <= n; i++)
    {
        nr_2 = nr_1 + nr_0;
        nr_0 = nr_1;
        nr_1 = nr_2;
    }
    return nr_2;
}

Probleme recursivitate

1. Avand un sir cu n elemente numere reale, sa se scrie o functie recursiva care calculeaza suma elementelor sirului.

int suma(int V[], int i) {
    if(i == -1)
        return 0;
    return V[i] + suma(V, i - 1);
}

2. Sa se determine cea mai mare cifra a unui numar intreg, de cel mult 9 cifre, citit de la tastatura.

3. Sa se determine cel mai mare divizor comun a doua numere naturale citite de la tastatura cu algoritmul lui EUCLID

4. Sa se converteasca un număr natural n , ale carui cifre se citesc de la tastatura, dat într-o baza 2≤b≤9, in baza 10.

5. Se citeste un vector cu n numere intregi. Sa se ordoneze crescator folosind tehnica recursiva.