Recursivitatea explicată pe înțelesul tuturor

La BAC informatică, recursivitatea apare aproape sigur la Subiectul I, într-o grilă de tipul „ce valoare are f(5)?” sau „ce se afișează la apelul f(123)?”. Mulți elevi o tratează ca pe ceva misterios, dar ideea e simplă: o funcție recursivă rezolvă o problemă mare folosind rezultatul aceleiași probleme, pe date mai mici. În articolul ăsta înțelegi cum funcționează recursivitatea în C++, de ce nu se apelează la nesfârșit și ce se întâmplă de fapt în memorie.

Ideea: o problemă definită prin ea însăși

Gândește-te la factorial: 5! = 5 · 4 · 3 · 2 · 1. Poți scrie la fel de bine 5! = 5 · 4!. Iar 4! = 4 · 3!, și tot așa, până la 0! = 1, pe care îl știi direct. Asta e o definiție recursivă:

• n! = 1, dacă n = 0 — condiția de oprire (cazul de bază);
• n! = n · (n−1)!, dacă n > 0 — relația de recurență.

În C++ se traduce aproape cuvânt cu cuvânt:

#include <iostream>
using namespace std;

int fact(int n)
{
    if (n == 0) return 1;          // condiția de oprire
    return n * fact(n - 1);        // apelul recursiv
}

int main()
{
    cout << fact(4);   // 24
    return 0;
}

Cele două ingrediente obligatorii

Orice funcție recursivă corectă are:

1. O condiție de oprire, pe care o verifici înainte de orice apel recursiv. Fără ea, funcția s-ar apela la nesfârșit, iar programul se oprește cu eroare când se umple memoria rezervată apelurilor (stiva).
2. Un apel pe date „mai mici”, care se apropie de condiția de oprire. fact(n - 1) se apropie de 0; fact(n + 1) nu s-ar opri niciodată.

Verifică mereu și că oprirea e atinsă pentru toate valorile permise. Dacă scrii if (n == 1) return 1; și cineva apelează fact(0), se ajunge la fact(-1), fact(-2)… și programul nu se mai oprește normal.

Ce se întâmplă în memorie: stiva de apeluri

Fiecare apel al unei funcții primește propria zonă de memorie, cu propriile copii ale parametrilor și variabilelor locale. Zonele acestea se pun una peste alta, pe stivă: ultimul apel început e primul care se termină. Pentru fact(4):

fact(4) = 4 * fact(3)          ← așteaptă
  fact(3) = 3 * fact(2)        ← așteaptă
    fact(2) = 2 * fact(1)      ← așteaptă
      fact(1) = 1 * fact(0)    ← așteaptă
        fact(0) = 1            ← condiția de oprire
      fact(1) = 1 * 1 = 1
    fact(2) = 2 * 1 = 2
  fact(3) = 3 * 2 = 6
fact(4) = 4 * 6 = 24

Sunt două faze: la dus se fac apelurile și fiecare rămâne „în așteptare” cu înmulțirea neterminată; la întors, pornind de la cazul de bază, se completează calculele în ordine inversă. În fiecare nivel, n are altă valoare — nu există un singur n care scade, ci patru copii diferite plus cea pentru fact(0).

Exemplul 2: suma cifrelor

Suma cifrelor lui 2026 este ultima cifră (6) plus suma cifrelor lui 202. Iar suma cifrelor lui 0 e 0.

int sumaCifre(int n)
{
    if (n == 0) return 0;
    return n % 10 + sumaCifre(n / 10);
}

sumaCifre(2026) = 6 + sumaCifre(202) = 6 + 2 + sumaCifre(20) = 6 + 2 + 0 + sumaCifre(2) = 6 + 2 + 0 + 2 + sumaCifre(0) = 10. Același tipar (n % 10 combinat cu un apel pe n / 10) stă în spatele multor grile: numărul de cifre, cifra maximă, numărul de cifre pare.

Exemplul 3: puterea, în două variante

Varianta directă folosește aⁿ = a · aⁿ⁻¹ și face n apeluri:

int putere(int a, int n)
{
    if (n == 0) return 1;
    return a * putere(a, n - 1);
}

Varianta rapidă observă că, pentru n par, aⁿ = (a^n/2)², deci înjumătățește exponentul:

long long putereRapida(long long a, int n)
{
    if (n == 0) return 1;
    if (n % 2 == 0)
    {
        long long t = putereRapida(a, n / 2);
        return t * t;
    }
    return a * putereRapida(a, n - 1);
}

Pentru 2¹⁰: exponenții parcurși sunt 10, 5, 4, 2, 1, 0 — doar 6 apeluri în loc de 11, iar rezultatul e 1024. Important: rezultatul lui putereRapida(a, n / 2) e salvat în t. Dacă ai scrie putereRapida(a, n / 2) * putereRapida(a, n / 2), ai face același calcul de două ori și ai pierde tot câștigul.

Contează unde pui instrucțiunile: înainte sau după apel

Asta e capcana preferată a grilelor. Compară:

#include <iostream>
using namespace std;

void inainte(int n)
{
    if (n > 0)
    {
        cout << n % 10;      // afișare la dus
        inainte(n / 10);
    }
}

void dupa(int n)
{
    if (n > 0)
    {
        dupa(n / 10);
        cout << n % 10;      // afișare la întors
    }
}

int main()
{
    inainte(1234);           // 4321
    cout << endl;
    dupa(1234);              // 1234
    return 0;
}

În inainte, fiecare apel afișează ultima cifră și abia apoi coboară, deci cifrele ies de la dreapta la stânga: 4321. În dupa, fiecare apel coboară întâi până la capăt și afișează la întoarcere, în ordine inversă apelurilor: 1234. Regula: ce e înainte de apelul recursiv se execută la dus, ce e după se execută la întors, în ordine inversă.

Recursiv sau iterativ?

Orice funcție recursivă poate fi rescrisă cu o structură repetitivă. Varianta iterativă folosește de obicei mai puțină memorie (nu ocupă stiva), dar cea recursivă e adesea mai scurtă și mai apropiată de definiția matematică. La Subiectul III poți folosi ambele, cu excepția cazului în care enunțul cere explicit una dintre ele. Atenție la funcțiile cu două apeluri recursive, ca Fibonacci scris direct: recalculează aceleași valori de foarte multe ori și devin foarte lente pentru n mare.