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. Orice recursivitate are două părți obligatorii:

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

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), calculatorul face:

factorial(4)
  → 4 * factorial(3)
        → 3 * factorial(2)
              → 2 * factorial(1)
                    → 1 * factorial(0)
                          → 1   (caz de baza)

Răspunsurile se întorc în ordine inversă: 1 → 1 → 2 → 6 → 24.

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;
}