Apel recursiv — coborâre și urcare

De ce contează?

Stai în ultima bancă și nu știi răspunsul. Pasezi întrebarea colegului din față, el o pasează mai departe, și tot așa până în prima bancă, unde cineva chiar știe. Răspunsul pornește înapoi pe același lanț, din mână în mână, până ajunge la tine. Recursivitatea funcționează exact așa: întrebarea coboară, răspunsul urcă.

Pasul recursiv: coborâre vs urcare

Un apel recursiv face un singur lucru simplu: reduce problema la o versiune mai mică și așteaptă rezultatul subproblemei. Nu rezolvă totul pe loc — deleagă.

Orice apel recursiv trece prin două faze distincte:

Coborârea (faza de apel): fiecare nivel reduce problema și lansează un apel mai mic. Nimic nu se calculează încă — nivelurile doar se înlănțuie și așteaptă. Coborârea se oprește când ajungem la cazul de bază, singurul care răspunde direct.
Urcarea (faza de return): din cazul de bază pornește un rezultat înapoi în sus. Fiecare nivel îl combină cu propria valoare și îl trimite mai departe părintelui.

Cheia: la coborâre întrebi, la urcare răspunzi. Calculul real are loc la urcare.

Trace pas cu pas

Urmărim factorial(4), unde factorial(n) = n * factorial(n - 1) și factorial(0) = 1.

Mai întâi coborârea — fiecare apel reduce n și așteaptă subproblema:

factorial(4) = 4 * factorial(3)         <- asteapta factorial(3)
  factorial(3) = 3 * factorial(2)       <- asteapta factorial(2)
    factorial(2) = 2 * factorial(1)     <- asteapta factorial(1)
      factorial(1) = 1 * factorial(0)   <- asteapta factorial(0)
        factorial(0) = 1                <- CAZ DE BAZA: raspunde direct

Acum urcarea — rezultatul cazului de bază se întoarce și se combină nivel cu nivel:

factorial(0) -> 1
factorial(1) -> 1 * 1  = 1
factorial(2) -> 2 * 1  = 2
factorial(3) -> 3 * 2  = 6
factorial(4) -> 4 * 6  = 24

Observă lanțul valorilor la urcare: 1 -> 1 -> 2 -> 6 -> 24. Săgeata în jos a fost coborârea (apeluri tot mai mici), săgeata în sus este urcarea (rezultate combinate).

Implementare C++

Adăugăm mesaje care fac vizibile cele două faze: o linie la coborâre (intrarea în apel) și o linie la urcare (valoarea returnată).

#include <iostream>
using namespace std;

long long factorial(int n) {
    cout << "coborare: intru in factorial(" << n << ")\n";

    if (n == 0) {                       // caz de baza
        cout << "  baza: factorial(0) = 1\n";
        return 1;
    }

    long long sub = factorial(n - 1);   // apel recursiv: astept subproblema
    long long rez = n * sub;            // combin la URCARE

    cout << "urcare: factorial(" << n << ") = " << n
         << " * " << sub << " = " << rez << "\n";
    return rez;
}

int main() {
    cout << "rezultat final: " << factorial(4) << "\n";   // 24
    return 0;
}

La rulare vezi întâi toate liniile de coborare (până la bază), apoi toate liniile de urcare în ordine inversă, terminând cu factorial(4) = 4 * 6 = 24.

Complexitate

Mărime	Valoare	De ce
Adâncimea recursiei	O(n)	un nivel pentru fiecare valoare de la `n` la `0`
Număr total de apeluri	O(n)	`n + 1` apeluri: `factorial(n)` ... `factorial(0)`
Lucru per apel	O(1)	o singură înmulțire și un return
Timp total	O(n)	O(n) apeluri × O(1) fiecare

Observația-cheie

Rezultatul nu se construiește la coborâre, ci la urcare. La coborâre fiecare apel doar pune o întrebare mai mică și se suspendă. Abia când cazul de bază trimite o valoare înapoi, fiecare nivel o combină cu n-ul lui. De-asta factorial(0) trebuie să răspundă primul — fără el, urcarea nu are de unde să pornească.

Greșeli frecvente

Uiți return la pasul recursiv: scrii factorial(n - 1); în loc de return n * factorial(n - 1);. Subproblema se calculează, dar valoarea ei se pierde la urcare și rezultatul final iese gunoi.
Combini greșit rezultatul subproblemei: scrii return factorial(n - 1); și uiți înmulțirea cu n. Apelul coboară corect, dar la urcare nu adaugi contribuția nivelului curent — primești mereu 1.
Crezi că totul se calculează la coborâre: aștepți valoarea finală încă din primul apel. Greșit: la coborâre nivelurile doar se înlănțuie; calculul vine la urcare.
Recursie care nu se micșorează: apelezi factorial(n) în loc de factorial(n - 1), sau lipsește cazul de bază. Coborârea nu atinge niciodată baza, deci nu începe urcarea — programul intră în stack overflow.

Vizualizare

Urmărește cum apelul „coboară” spre cazul de bază (săgeata ← spre apeluri tot mai mici), apoi cum rezultatele „urcă” înapoi combinându-se nivel cu nivel (săgeata → spre răspunsul final).

Indiciu

Citește vizualizarea pe două direcții: săgeata ← este coborârea (pui întrebări tot mai mici), săgeata → este urcarea (răspunsurile se întorc și se combină). Valoarea finală apare doar la capătul săgeții → .

Recapitulare

Apelul recursiv reduce problema și așteaptă rezultatul subproblemei; coborârea doar înlănțuie apeluri, fără să calculeze.
Calculul real are loc la urcare: din cazul de bază rezultatul se întoarce și fiecare nivel îl combină cu valoarea lui (1 -> 1 -> 2 -> 6 -> 24 pentru factorial(4)).
Pasul recursiv corect este return n * factorial(n - 1); — fără return sau fără combinarea cu n, rezultatul de la urcare se pierde sau iese greșit.