Funcții recursive

Funcția recursivă reprezintă o construcție în care funcția se apelează pe ea însăși.

Funcția recursivă pentru factorial

Să luăm, de exemplu, calculul factorialului, care folosește formula n! = 1 * 2 * … * n. Practic, pentru a găsi factorialul unui număr, înmulțim toate numerele până la acel număr. De exemplu, factorialul numărului 4 este 24 = 1 * 2 * 3 * 4, iar factorialul numărului 5 este 120 = 1 * 2 * 3 * 4 * 5.

Definim metoda pentru calcularea factorialului:

int Factorial(int n)
{
   if (n == 1) return 1;
   return n * Factorial(n - 1);
}

La crearea unei funcții recursive, trebuie să existe neapărat o condiție de bază de la care începe calculul funcției. În cazul factorialului, aceasta este factorialul numărului 1, care este egal cu 1. Factorialele tuturor celorlalte numere pozitive vor începe cu calculul factorialului numărului 1, care este 1.

La nivelul limbajului de programare, pentru returnarea valorii de bază se folosește operatorul return:

if (n == 1) return 1;

Adică, dacă numărul introdus este 1, se returnează 1.

O altă caracteristică a funcțiilor recursive: toate apelurile recursive trebuie să se refere la subfuncții care, în cele din urmă, se reduc la condiția de bază:

return n * Factorial(n - 1);

Astfel, când transmitem în funcție un număr diferit de 1, la apelurile recursive ulterioare, în subfuncții se va transmite de fiecare dată un număr mai mic cu o unitate. În cele din urmă, ajungem la situația în care numărul este 1 și se folosește condiția de bază. Aceasta se numește recursie descendentă.

Să folosim această funcție:

int Factorial(int n)
{
   if (n == 1) return 1;
   return n * Factorial(n - 1);
}

int factorial4 = Factorial(4);  // 24
int factorial5 = Factorial(5);  // 120
int factorial6 = Factorial(6);  // 720

Console.WriteLine($"Factorialul numărului 4 = {factorial4}");
Console.WriteLine($"Factorialul numărului 5 = {factorial5}");
Console.WriteLine($"Factorialul numărului 6 = {factorial6}");

Să analizăm pas cu pas ce se întâmplă în cazul apelului Factorial(4).

Mai întâi se verifică dacă numărul este egal cu 1:

if (n == 1) return 1;

Dar la început n este 4, deci această condiție este falsă și, în consecință, se execută codul:

return n * Factorial(n - 1);

Practic, avem:

return 4 * Factorial(3);

Apoi se execută expresia:

Factorial(3)

Din nou, n nu este egal cu 1, deci se execută codul:

return n * Factorial(n - 1);

Practic:

return 3 * Factorial(2);

Apoi se execută expresia:

Factorial(2)

Din nou, n nu este egal cu 1, deci se execută codul:

return n * Factorial(n - 1);

Practic:

return 2 * Factorial(1);

Apoi se execută expresia:

Factorial(1)

Acum n este egal cu 1, deci se execută codul:

if (n == 1) return 1;

Și se returnează 1. În cele din urmă, expresia:

Factorial(4)

Se rezumă la:

4 * 3 * 2 * Factorial(1)

Funcția recursivă pentru Fibonacci

Un alt exemplu comun de funcție recursivă este funcția care calculează numerele Fibonacci. Elementul n din secvența Fibonacci se determină prin formula: f(n)=f(n-1) + f(n-2), unde f(0)=0 și f(1)=1. Secvența Fibonacci va arăta astfel: 0 (elementul 0), 1 (elementul 1), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, .... Pentru a determina numerele acestei secvențe, definim următoarea metodă:

int Fibonacci(int n)
{
   if (n == 0 || n == 1) return n;
   return Fibonacci(n - 1) + Fibonacci(n - 2);
}

int fib4 = Fibonacci(4);
int fib5 = Fibonacci(5);
int fib6 = Fibonacci(6);

Console.WriteLine($"Al 4-lea număr Fibonacci = {fib4}");
Console.WriteLine($"Al 5-lea număr Fibonacci = {fib5}");
Console.WriteLine($"Al 6-lea număr Fibonacci = {fib6}");

Aici condiția de bază arată astfel:

if (n == 0 || n == 1) return n;

Adică, dacă căutăm elementul 0 sau 1 al secvenței, se returnează acest număr - 0 sau 1. În caz contrar, se returnează rezultatul expresiei Fibonacci(n - 1) + Fibonacci(n - 2).

Recursii și cicluri

Acestea sunt exemple simple de funcții recursive care au scopul de a oferi o înțelegere a funcționării recursiei. În același timp, pentru ambele funcții putem folosi construcții ciclice în locul recursiei.

De obicei, alternativele bazate pe cicluri funcționează mai rapid și sunt mai eficiente decât recursia. De exemplu, calculul numerelor Fibonacci folosind cicluri:

static int Fibonacci2(int n)
{
   int result = 0;
   int b = 1;
   int tmp;

   for (int i = 0; i < n; i++)
   {
       tmp = result;
       result = b;
       b += tmp;
   }

   return result;
}

În același timp, în anumite situații, recursia oferă o soluție elegantă, de exemplu, la parcurgerea diferitelor structuri de tip arbore, cum ar fi arborele de directoare și fișiere.