Utilitate

Recursivitatea constitue o tehnică de a descrie într-o manieră elegantă şi concisă prelucrări de natură repetitivă.
De multe ori întâlnim procese care se exprimă în termeni recursivi. La matematică, cea mai simplă şi familiară funcţie exprimată în termeni recursivi este factorialul:

            n ! = 1                  dacă n <= 1

            n ! = N × (N-1)!  dacă n > 1

Folosind această definiţie, putem descrie o funcţie recursivă de calcul al factorialului unui număr natural:

unsigned long fact(int n)
{
      if(!n) return 1;
      return  n*fact (n-1);
}

Deşi simplu, acesta nu este cel mai bun exemplu pentru a ilustra recursivitatea, pentru că funcţia factorial poate fi descrisă în mod echivalent astfel:

            n ! =1                   dacă n = 0

            n ! =1·2·3·....·n dacă n > 0

Această definiţie conduce la următoarea funcţie iterativă de calcul:

unsigned long fact(int n)
{
      unsigned long f=1;
      for(int i=1; i<=n; i++) f*=i;
      return f;
}

Dacă realizăm o comparaţie între varianta iterativă de calcul al factorialului şi varianta recursivă, se observă că varianta recursivă este dezavantajoasă, deoarece necesită timp de execuţie suplimentar pentru operaţiile cu stivă (la apel – alocarea memoriei necesare pentru parametrul funcţiei, pentru valoarea calculată de funcţie şi pentru adresa de revenire, iar la încheierea execuţiei unui apel – eliberarea memoriei alocate).