De ce contează?
Ai 5 cărți și vrei să știi în câte ordini le poți aranja pe raft. Prima poziție are 5 variante, a doua 4, a treia 3 și tot așa: 5 × 4 × 3 × 2 × 1 = 120. Asta este factorialul — numărul de permutări ale unui set, fundamental în combinatorică și probabilitate.
Definiție
n! = n × (n−1) × (n−2) × ... × 2 × 1
Cazuri speciale: 0! = 1, 1! = 1
| n | n! |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 10 | 3.628.800 |
| 12 | 479.001.600 |
Factorialul crește extrem de rapid. Chiar și long long (max ~9.2 × 10¹⁸) nu ține decât până la 20! = 2.432.902.008.176.640.000. Pentru n > 20 ai nevoie de numere mari (big integer) sau de calcul modulo un prim.
Implementare C++ — iterativă
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long fact = 1; // long long pentru valori mari
for (int i = 2; i <= n; i++) {
fact *= i;
}
cout << n << "! = " << fact << endl;
return 0;
}Exemplu: Input 5 → 5! = 120
Observă că bucla pornește de la 2, nu de la 1 — înmulțirea cu 1 este inutilă. Pentru n = 0 sau n = 1, bucla nu rulează deloc și fact rămâne 1 — corect prin definiție.
Varianta recursivă
long long factorial(int n) {
if (n <= 1) return 1; // caz de baza
return n * factorial(n - 1); // pas recursiv
}Elegantă și ușor de citit, dar consumă O(n) memorie de stivă — evita-o pentru n mare.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Iterativ | O(n) | O(1) |
| Recursiv | O(n) | O(n) — stiva de apeluri |
Vizualizare
Urmărește cum apelurile recursive coboară până la cazul de bază, apoi se recompun înmulțind la întoarcere:
Greșeala 1: Folosești int în loc de long long. 13! depășește int. Declară și calculează cu long long mereu.
Greșeala 2: Inițializezi fact = 0 în loc de fact = 1. Produsul pornit de la 0 rămâne 0.
Greșeala 3: Uiți că bucla for(i=2; i<=0; ...) nu rulează pentru n=0, deci fact rămâne 1 — corect prin definiție. Dacă n poate fi negativ, adaugă o verificare înainte de buclă.
Greșeala 4: La varianta recursivă, nu ai caz de bază pentru n=0 sau n=1 și intri în recursie infinită. Asigură-te că returnezi 1 pentru n <= 1.