Recursivitate în C

tip f(parametri) {
    if (caz_de_baza) return valoare;
    return ... f(parametri_mai_mici) ...;
}

Ce face Recursivitate

O funcție recursivă rezolvă o problemă apelându-se pe ea însăși pentru o variantă mai mică a aceleiași probleme. Are nevoie de un caz de bază, în care răspunde direct, fără alt apel; altfel apelurile nu se mai termină.

Fiecare apel ocupă spațiu pe stivă (parametrii, variabilele locale, adresa de întoarcere). Stiva are o dimensiune limitată (de obicei câțiva MB), deci o recursivitate foarte adâncă oprește programul cu „stack overflow”. Pentru parcurgeri simple, o buclă este de obicei mai potrivită.

Recursivitatea este naturală pentru structuri care se definesc tot recursiv: arbori, directoare cu subdirectoare, expresii, algoritmi precum quicksort sau căutarea binară.

Exemple

Exemplul 1: Factorial

5! = 5 · 4!, iar cazul de bază este 0! = 1. Rezultatul crește repede, de aceea tipul este unsigned long long.

#include <stdio.h>

unsigned long long factorial(unsigned n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

int main(void) {
    for (unsigned i = 0; i <= 20; i += 5) {
        printf("%u! = %llu\n", i, factorial(i));
    }
    return 0;
}

Rezultat

0! = 1
5! = 120
10! = 3628800
15! = 1307674368000
20! = 2432902008176640000

Exemplul 2: Căutare binară recursivă

Tabloul este sortat. La fiecare pas, funcția compară cu elementul din mijloc și caută doar în jumătatea potrivită.

#include <stdio.h>

int cauta(const int *t, int stanga, int dreapta, int x) {
    if (stanga > dreapta) return -1;          // caz de bază: nu există
    int mijloc = stanga + (dreapta - stanga) / 2;
    if (t[mijloc] == x) return mijloc;
    if (t[mijloc] < x) return cauta(t, mijloc + 1, dreapta, x);
    return cauta(t, stanga, mijloc - 1, x);
}

int main(void) {
    int coduri[] = {700, 1100, 2400, 3100, 4100, 5500, 6600};
    printf("4100 este la poziția %d\n", cauta(coduri, 0, 6, 4100));
    printf("1000 este la poziția %d\n", cauta(coduri, 0, 6, 1000));
    return 0;
}

Rezultat

4100 este la poziția 4
1000 este la poziția -1

Exemplul 3: Afișarea unui număr cifră cu cifră

Apelul recursiv vine înainte de afișare, deci cifrele apar în ordinea corectă, de la stânga la dreapta.

#include <stdio.h>

void cifre(unsigned n) {
    if (n >= 10) {
        cifre(n / 10);
    }
    printf("[%u]", n % 10);
}

int main(void) {
    cifre(2026);
    printf("\n");
    return 0;
}

Rezultat

[2][0][2][6]

Greșeli frecvente

• Lipsește cazul de bază sau nu este atins (de exemplu factorial(-1) cu parametru int). Apelurile continuă până se umple stiva.
• Calculezi Fibonacci recursiv cu două apeluri (fib(n-1) + fib(n-2)) pentru valori mari. Numărul de apeluri crește exponențial; folosește o buclă.
• Pui tablouri mari ca variabile locale într-o funcție recursivă. Fiecare apel le pune din nou pe stivă.

Comenzi înrudite

• Funcții și prototipuri: Cum definești și declari funcții în C: tipul rezultatului, parametrii, prototipul și transmiterea argumentelor prin valoare.
• bsearch: Caută rapid un element într-un tablou sortat (căutare binară) și întoarce un pointer la el sau NULL.
• qsort: Sortează un tablou de orice tip, folosind o funcție de comparare scrisă de tine.
• while și do-while: Repetă un bloc cât timp o condiție este adevărată; do-while rulează blocul cel puțin o dată, apoi verifică.