Recursivitatea

Recursivitatea este proprietatea unei entitati (algoritm, program, structura de date, figura etc.) de a putea fi descrisa prin entitati de acelasi tip cu ea insasi. Recursivitatea este larg folosita in matematica si este, tot o data, o tehnica importanta de elaborare a algoritmilor. Vom arata, de asemenea, ca si unele structuri de date au caracter recursiv, ceeace faciliteaza prelucrarea lor prin algoritmi recursivi.
 
Exista o stransa legatura intre recursivitate si rationamentul inductiv. Amintim ca, in acest rationament, se stabileste ca o anumita proprietate P este valabila pentru toate elementele unui sir de entitati E1, E2, E3, ... Ek, Ek+1, .... 

Rationamentul contine doua etape:

  1. se stabileste ca proprietatea P are loc pentru elementul E1 (eventual pentru un numar finit de elemente E1, E2, ..., Em);
  2. se demonstreaza ca, daca proprietatea P are loc pentru un element oarecare Ek, ea are loc si pentru elementul urmator Ek+1, deci este valabila pentru toate elementele sirului.

Functii, proceduri si metode recursive

Functia recursiva este o functie in corpul careia exista apeluri la ea insasi. In mod similar, o procedura in corpul careia exista apeluri la ea insasi este recursiva.

In programarea orientata pe obiecte, functiile si procedurile se realizeaza sub forma de metode. In consecinta, functiile si procedurile recursive sunt metode recursive.
 
Exemple de functii recursive:

1. Functia factorial:
      fact(0)=1;
      fact(k)=k*fact(k-1) pentru k>0

2. Functia lui Fibonacci:
      fib(0)=fib(1)=1
      fib(k)=fib(k-1)+fib(k-2) pentru k>1

3. Functia lui Ackerman
    Este un exemplu de functie care creste mai rapid decat cea exponentiala si se defineste astfel:
      Fie m si n numere naturale;
      ack(0, n) = n+1;
      ack(m, 0) = ack(m-1, 1)  pentru m>0;
      ack(m, n) = ack(m-1, ack(m, n-1)) pentru m>0 si n>0.
    Remarcam ca, in ultima linie a acestei definitii, are loc o dubla invocare recursiva a functiei: o data pentru calcularea celui de al doilea argument si inca o data pentru calcularea valorii functiei.

Din exemplele de mai sus, constatam urmatoarele:

Exista si posibilitatea ca recursia sa fie indirecta: in corpul functiei f este invocata functia g, iar in corpul functiei g este invocata functia f. Cercul acestor invocari succesive poate sa contina mai mult de doua functii.
 
Procedurile nu au valoare intoarsa, ci numai efect lateral. In consecinta, folosirea procedurilor recursive se bazeaza pe cumularea efectelor laterale, care consta in modificarea valorilor unor variabile globale sau valorilor parametrilor procedurii. In limbajul Java nu exista variabile globale, dar pot fi modificate valorile unor campuri ale clasei careia ii apartine metoda recursiva sau ale unor componente ale obiectelor primite ca parametri.

Comparatie intre iteratie si recursie

Aceeasi functie poate fi, de regula, calculata atat printr-un algoritm iterativ, cat si prin unul recursiv. Uneori insa, iteratia este mult mai rapida decat recursia si consuma mai putina memorie. In schimb, utilizarea functiilor sau procedurilor recursive este mai eleganta si face algoritmul mai usor de inteles si de verificat. In plus, folosirea recursivitatii este o tehnica foarte eficienta de concepere a algoritmilor. Din aceasta cauza, multi algoritmi sunt conceputi mai intai in varianta lor recursiva si apoi, numai daca aceasta varianta necesita timp de calcul sau memorie prea mare, se cauta si o varianta iterativa.
 
De foarte multe ori, trecerea de la varianta recursiva la cea iterativa a algoritmului se face inlocuind functia recursiva printr-un ciclu. De exemplu, pentru calcularea factorialului, se poate folosi fie functia recursiva

    static long factorial(long n) throws Exception {
      if(n<0) throw new Exception("Factorial arg<0: "+n);
      if(n==0) return 1; // conditia de incheiere a recursiei
      return n*factorial(n-1); // invocarea recursiva
    }

fie varianta iterativa

    static long fact(long n) throws Exception {
      if(n<0) throw new Exception("Factorial arg<0: "+n);
      long f=1; // initializarea ciclului
      for(long i=2; i<=n; i++) f*=i; // ciclul de iterare
      return f;
    }

Complexitatea ambelor functii este liniara O(n)

Vom arata totusi, ca exista si situatii in care inlocuirea recursiei prin iteratie necesita folosirea unei structuri de stiva.

Exemplu
In fisierul Fibonacci.java se da un exemplu de aplicatie in care se testeaza doua variante de calcul al functiei Fibonacci: varianta recursiva, care respecta definitia data mai sus, si varianta iterativa. Argumentul functiei se da ca argument in linia de comanda. Pentru fiecare din aceste variante se determina si timpul de calcul (in milisecunde). In acest scop, inainte si dupa invocarea metodei respective se invoca metoda System.currentTimeMillis(), care intoarce timpul indicat de ceasul sistemului, si se face diferenta, obtinand timpul de calcul in milisecunde. Este posibil ca, pentru valori mici ale argumentului functiei, durata de calcul in ambele variante sa fie 0 (adica mai mica de o milisecunda). Se consta insa ca la valori mai mari ale argumentului (peste 25) diferenta dintre cele doua variante devine din ce in ce mai mare, in defavoarea celei recursive. Memoria ocupata este, de asemenea, mult mai mare la varianta recursiva, unde se pun pe stiva sistemului toate datele de la invocarile intermediare ale functiei, in timp ce in varianta iterativa este necesar sa se memoreze de la o iteratie la alta numai doua valori: f1=fib(i-1) si f2=fib(i-2).

Explicatia este ca cei doi algoritmi folositi pentru calculul functiei Fibonacci au complexitati diferite. In varianta iterativa exista un singur ciclu, care se parcurge de n-2 ori, deci algoritmul are complexitate liniara O(n). In varianta recursiva, numarul de apeluri recursive ale functiei fibonacci(k) se obtine ca suma unei progresii geometrice cu ratia 2 si deci este de ordinul 2n. Intr-adevar, pentru calcularea lui fibonacci(n) este necesar sa se calculeze fibonacci(n-1) si fibonacci(n-2). Pentru calcularea fiecareia din aceste valori sint necesare alte doua apeluri ale functiei fibonacci si asa mai departe, pana se ajunge la fibonacci(1). Complexitatea algoritmului recursiv este deci, in acest caz, exponentiala O(2n).



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati