Factorial — prima ta recursivitate

Ce este recursivitatea?

O funcție este recursivă când se apelează pe ea însăși cu un argument mai mic. O folosim pentru că unele probleme se definesc natural prin ele însele: factorialul, parcurgerea unui arbore, șirul lui Fibonacci. În loc să scriem un cod complicat cu bucle, descriem doar cum se reduce problema la una mai simplă — restul îl face calculatorul, repetând automat reducerea.

Orice recursivitate are două părți obligatorii:

1. Cazul de bază — condiția de oprire (fără el, funcția rulează la infinit)
2. Pasul recursiv — problema se reduce la o versiune mai mică

Lipsa oricăreia dintre ele este greșeala clasică: fără caz de bază obții recursie infinită; fără pas care micșorează argumentul, nu ajungi niciodată la caz de bază.

Factorialul

Definiția matematică:

n! = n × (n-1) × ... × 2 × 1
0! = 1 (prin convenție)

Rescrisă recursiv: n! = n × (n-1)!

Implementare recursivă C++

#include <iostream>
using namespace std;

long long factorial(int n) {
    if (n == 0) return 1;      // caz de baza
    return n * factorial(n - 1); // pas recursiv
}

int main() {
    cout << factorial(5) << endl;  // 120
    cout << factorial(10) << endl; // 3628800
    return 0;
}

Stiva de apeluri

Când apelăm factorial(4), fiecare apel îl așteaptă pe cel mai mic. Mai întâi se coboară până la cazul de bază, punând câte un cadru pe stivă, apoi se urcă înmulțind răspunsurile întoarse:

COBORÂRE (apeluri puse pe stivă)        URCARE (returnuri, de jos în sus)
─────────────────────────────────      ────────────────────────────────────
factorial(4)  = 4 × factorial(3)  ┐                        ↑  24 = 4 × 6
  factorial(3) = 3 × factorial(2) │                        ↑   6 = 3 × 2
    factorial(2) = 2 × factorial(1)│                       ↑   2 = 2 × 1
      factorial(1) = 1 × factorial(0)│                     ↑   1 = 1 × 1
        factorial(0) = 1  ◄── caz de bază ──────────────►  1

Cele cinci apeluri stau simultan pe stivă, fiecare reținând cu ce trebuie să își înmulțească rezultatul întors. La cazul de bază factorial(0) = 1 oprirea declanșează urcarea: răspunsurile se întorc în ordine inversă, înmulțindu-se pe rând — 1 → 1 → 2 → 6 → 24.

Produsele parțiale se construiesc pe drumul de întoarcere, fiecare folosindu-l pe cel de dedesubt:

Vizualizare

Urmărește cum fiecare apel factorial(n) se adaugă pe stivă până la cazul de bază, apoi cum returnurile se înmulțesc înapoi, de jos în sus:

Implementare iterativă (comparație)

long long factorialIterativ(int n) {
    long long rezultat = 1;
    for (int i = 2; i <= n; i++) {
        rezultat *= i;
    }
    return rezultat;
}

Ambele variante fac aceleași n înmulțiri, deci au același timp. Diferența este la spațiu: versiunea recursivă ține pe stivă n apeluri simultan, pe când cea iterativă folosește o singură variabilă.