Recursivitate

Recursivitatea este un mecanism general de elaborare a algoritmilor. O functie se numeste recursiva daca ea se autoapeleaza, fie direct (in definitia ei, se face apel la ea insasi), fie indirect (functia X apeleaza functia Y, care apeleaza functia X).

Recursivitatea a aparut din necesitati practice date de transcrierea directa a formulelor matematice recursive. Apoi, acest mecanism a fost extins, fiind utilizat in elaborarea multor algoritmi.

Pornim de la un exemplu : Sa se calculeze n !

Se observa ca n !=(n-1) !*n si se stie ca 0 !=1. Asadar :

5 !=4 !*5

4 !=3 !*4

3 !=2 !*1

1 !=0 !*1

0 !=1 (prin conventie matematica)

Definitia recursiva a lui n ! este :

Functia recursiva se va scrie astfel:

long factorial(int n)

{if(n==0) return 1;

else return factorial(n-1)*n;}

void main()

{cout<<factorial(5) ;}

Se observa ca functia factorial se autoapeleaza. Autoapelul se realizeaza prin instructiunea return factorial(n-1)*n.

Sa vedem care este mecanismul prin care subprogramele se pot autoapela. Se stie ca la apelul fiecarui subprogram, se genereaza un nou nivel in segmentul de stiva, corespunzator acelui apel. Pe acel nivel se memoreaza :

- valorile parametrilor transmisi prin valoare

- adresele parametrilor transmisi prin referinta

- variabilele locale

- adresa de revenire din functie

In capitolul anterior s-au discutat proprietatile structurii de date numita stiva. Exact aceleasi proprietati are si segmentul de stiva, numai ca acesta este gestionat automat de catre calculator, nu de catre programator. De fiecare data cand o functie se autoapeleaza, se creeaza un nou nivel in segmentul de stiva.

Fiecare apel de functie lucreaza cu datele aflate pe nivelul corespunzator acelui apel. La iesirea din apelul unei functii, nivelul respectiv se elibereaza si datele aflate acolo se pierd. Exista posibilitatea ca subprogramul sa lucreze direct cu variabilele globale, dar in acest caz, subprogramul isi pierde independenta.

Cum gandim un algoritm recursiv ?

Iata cateva exemple de rationament recursiv :

- O camera de luat vederi are in obiectiv un televizor care transmite imaginile primite de la camera. In televizor se vede un televizor in care se vede un televizor…

- Anunt : Azi nu se fumeaza !

O gandire recursiva exprima concentrat o anumita stare, care se repeta la infinit. Aceasta gandire se aplica in elaborarea algoritmilor recursivi cu o modificare esentiala: adaugarea conditiei de terminare. In absenta acestei conditii nu se poate vorbi despre un algoritm deoarece acestia sunt finiti. Din acest punct de vedere, exemplele de mai sus nu sunt corecte.Atunci cand gandim un algoritm recursiv, privim problema la un anumit nivel. Ce se intampla la acel nivel se va intampla la toate celelalte.

Observatii :

- In cazul unui numar mare de autoapelari, exista posibilitatea ca segmentul de stiva sa se ocupe total, caz in care programul se va termina cu eroarea STACK OVERFLOW. Aceasta se intampla mai ales atunci cand conditia de terminare este pusa gresit si subprogramul se apeleaza la nesfarsit.

- Pentru orice algoritm recursiv exista unul iterativ care rezolva aceeasi problema.

- Mecanismul recursivitatii inlocuieste instructiunile repetitive.

- Datorita faptului ca la fiecare autoapel se ocupa o zona de memorie, recursivitatea este eficienta numai daca numarul de autoapelari nu este prea mare pentru a nu se ajunge la umplerea zonei de memorie alocata.

- Recursivitatea ofera avantajul unor solutii mai clare pentru probleme si a unei lungimi mai mici a programului. Ea prezinta insa dezavantajul unui timp mai mare de executie si a unui spatiu de memorie alocata mai mare. Este de preferat ca atunci cand programul recursiv poate fi transformat cu usurinta intr-unul iterativ sa se faca apel la cel din urma (vezi sirul lui Fibonacci)

Exemplu de functii ce calculeaza produsul primelor n numere naturale :

Functia iterativa int f(int n) {int i=1, P=1; while (i<=n) {P=P*i ; i++ ;} return P ;} void main() {int n=5; cout<<f(n);}

Functia recursiva 1 int n; int f(int i) {if (i<=n) return i*f(i+1); else return 1 ;} void main() {n=5; cout<<f(1);}

Functia recursiva 2 int f(int i) {if (i>1) return i*f(i-1); else return 1 ;} void main() {int n=5; cout<<f(n);}

Observati ca la primele doua subprograme conditia de continuare (a iteratiei respectiv a autoapelului este aceeasi)

Recomandare : inainte de elaborarea algoritmilor recusivi generati mai intai subprogramul iterativ apoi treceti-l in subprogram recursiv.