Funcții recursive

Să analizăm separat funcțiile recursive. Principala diferență între funcțiile recursive și metodele obișnuite constă în faptul că o funcție recursivă se poate apela pe sine.

De exemplu, să analizăm o funcție care calculează factorialul unui număr:

static int factorial(int x){  
   
   if (x == 1){  
   
       return 1;  
   }  
   return x * factorial(x - 1);  
}

La început, este verificată condiția: dacă numărul introdus este diferit de 1, înmulțim acest număr cu rezultatul aceleiași funcții, în care se transmite ca parametru numărul x-1. Astfel, se produce o coborâre recursivă. Procesul continuă până ajungem la momentul în care valoarea parametrului este egală cu unu.

O funcție recursivă trebuie să aibă neapărat o variantă de bază, care utilizează operatorul return și care este plasată la începutul funcției. În cazul factorialului, aceasta este: if (x == 1) return 1;.

oate apelurile recursive trebuie să facă referire la subfuncții care, în cele din urmă, converg spre varianta de bază. Astfel, atunci când transmitem în funcție un număr pozitiv, la fiecare apel recursiv se transmite un număr cu o unitate mai mic. În final, ajungem la situația în care numărul devine 1, iar varianta de bază este utilizată.

Cu toate acestea, trebuie menționat că pentru calculul factorialului există soluții mai eficiente bazate pe cicluri:

static int factorial(int x){  
   int result = 1;  
   for (int i = 1; i <= x; i++)  
   {  
       result *= i;  
   }  
   return result;  
}

Un alt exemplu obișnuit de funcție recursivă este funcția care calculează numerele Fibonacci. În teorie, al n-lea termen din șirul Fibonacci este definit prin formula: f(n) = f(n-1) + f(n-2), unde f(0) = 0 și f(1) = 1.

static int fibonachi(int n){  

   if (n == 0){  
       return 0;  
   }  
   if (n == 1){  
       return 1;  
   }  
   else{  
       return fibonachi(n - 1) + fibonachi(n - 2);  
   }  
}

Acest exemplu utilizează recursivitatea pentru a calcula numărul Fibonacci corespunzător valorii n transmise ca parametru.