Recursivitatea

Recursivitatea este proprietatea unei entități (algoritm, program, structură de date, figură etc.) de a putea fi descrisă prin entități de acelasi tip cu ea însăși. Recursivitatea este larg folosită în matematică și este, tot o dată, o tehnică importantă de elaborare a algoritmilor. Vom arata, de asemenea, că și unele structuri de date au caracter recursiv, ceeace facilitează prelucrarea lor prin algoritmi recursivi.
 
Există o strânsa legătură între recursivitate și raționamentul inductiv. Amintim că, în acest raționament, se stabilește că o anumită proprietate P este valabilă pentru toate elementele unui șir de entități E1, E2, E3, ... Ek, Ek+1, .... 

Raționamentul conține doua etape:

  1. se stabilește că proprietatea P are loc pentru elementul E1 (eventual pentru un număr finit de elemente E1, E2, ..., Em);
  2. se demonstrează că, dacă proprietatea P are loc pentru un element oarecare Ek, ea are loc și pentru elementul următor Ek+1, deci este valabilă pentru toate elementele șirului.

Funcții, proceduri și metode recursive

Funcția recursivă este o funcție în corpul căreia există apeluri la ea însăși. În mod similar, o procedură în corpul căreia există apeluri la ea însăși este recursivă.

În programarea orientată pe obiecte, funcțiile și procedurile se realizează sub formă de metode. În consecință, funcțiile și procedurile recursive sunt metode recursive.
 
Exemple de funcții recursive:

1. Funcția factorial:
      fact(0)=1;
      fact(k)=k*fact(k-1) pentru k>0

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

3. Funcția lui Ackerman
    Este un exemplu de funcție care creste mai rapid decat cea exponențială și se definește astfel:
      Fie m și 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.
    Remarcăm că, în ultima linie a acestei definiții, are loc o dublă invocare recursiva a funcției: o dată pentru calcularea celui de al doilea argument și încă o dată pentru calcularea valorii funcției.

Din exemplele de mai sus, constatăm urmatoarele:

Există și posibilitatea ca recursia sa fie indirectă: în corpul funcției f este invocată funcția g, iar în corpul funcției g este invocată funcția f. Cercul acestor invocări succesive poate sa conțină mai mult de două funcții.
 
Procedurile nu au valoare întoarsă, ci numai efect lateral. În consecință, folosirea procedurilor recursive se bazează pe cumularea efectelor laterale, care constă în modificarea valorilor unor variabile globale sau valorilor parametrilor procedurii. În limbajul Java nu există variabile globale, dar pot fi modificate valorile unor câmpuri ale clasei căreia îi aparține metoda recursivă sau ale unor componente ale obiectelor primite ca parametri.

Comparație între iterație și recursie

Aceeași funcție poate fi, de regulă, calculată atât printr-un algoritm iterativ, cât și prin unul recursiv. Uneori însă, iterația este mult mai rapidă decât recursia și consumă mai puțină memorie. În schimb, utilizarea funcțiilor sau procedurilor recursive este mai elegantă și face algoritmul mai ușor de înțeles și de verificat. În plus, folosirea recursivității este o tehnică foarte eficientă de concepere a algoritmilor. Din aceasta cauză, mulți algoritmi sunt concepuți mai întâi în varianta lor recursivă și apoi, numai dacă aceasta variantă necesită timp de calcul sau memorie prea mare, se caută și o variantă iterativă.
 
De foarte multe ori, trecerea de la varianta recursivă la cea iterativă a algoritmului se face înlocuind funcția recursivă printr-un ciclu. De exemplu, pentru calcularea factorialului, se poate folosi fie funcția recursivă

    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 recursivă
    }

fie varianta iterativă

    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 funcții este liniară O(n)

Vom arăta totuși, că există și situații în care înlocuirea recursiei prin iterație necesită folosirea unei structuri de stivă.

Exemplu
În fisierul Fibonacci.java se dă un exemplu de aplicație în care se testează doua variante de calcul al funcției Fibonacci: varianta recursivă, care respectă definiția dată mai sus, și varianta iterativă. Argumentul funcției se dă ca argument în linia de comandă. Pentru fiecare din aceste variante se determină și timpul de calcul (în milisecunde). În acest scop, înainte și după invocarea metodei respective se invocă metoda System.currentTimeMillis(), care intoarce timpul indicat de ceasul sistemului, și se face diferența, obținând timpul de calcul în milisecunde. Este posibil ca, pentru valori mici ale argumentului funcției, durata de calcul în ambele variante să fie 0 (adică mai mică de o milisecundă). Se constată însă că la valori mai mari ale argumentului (peste 25) diferența dintre cele doua variante devine din ce în ce mai mare, în defavoarea celei recursive. Memoria ocupată este, de asemenea, mult mai mare la varianta recursivă, unde se pun pe stiva sistemului toate datele de la invocările intermediare ale funcției, în timp ce în varianta iterativă este necesar să se memoreze de la o iterație la alta numai doua valori: f1=fib(i-1) și f2=fib(i-2).

Explicația este că cei doi algoritmi folosiți pentru calculul funcției Fibonacci au complexități diferite. În varianta iterativă există un singur ciclu, care se parcurge de n-2 ori, deci algoritmul are complexitate liniară O(n). În varianta recursivă, numarul de apeluri recursive ale funcției fibonacci(k) se obține ca suma unei progresii geometrice cu rația 2 și deci este de ordinul 2n. Într-adevar, pentru calcularea lui fibonacci(n) este necesar sa se calculeze fibonacci(n-1) si fibonacci(n-2). Pentru calcularea fiecăreia din aceste valori sunt necesare alte două apeluri ale funcției fibonacci și așa mai departe, până se ajunge la fibonacci(1). Complexitatea algoritmului recursiv este deci, în acest caz, exponentială O(2n).



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați