階乘（Factorial）與階乘求和是遞迴、迭代、累積模式的入門經典題目。本文系統整理：單一數階乘計算、1!+2!+...+n! 求和、單迴圈優化技巧、大數階乘處理、遞迴與迭代效能對比，並提供溢位檢測與任意精度擴展方向。
long long factorialIterative(int n) {
if (n < 0) return -1; // 錯誤碼
long long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
long long factorialRecursive(int n) {
if (n < 0) return -1;
if (n <= 1) return 1;
return n * factorialRecursive(n - 1);
}
long long sumFactorialNaive(int n) {
long long sum = 0;
for (int i = 1; i <= n; i++) {
long long fact = 1;
for (int j = 1; j <= i; j++) {
fact *= j;
}
sum += fact;
}
return sum;
}
long long sumFactorialOptimized(int n) {
long long sum = 0;
long long currentFact = 1; // 1! = 1
for (int i = 1; i <= n; i++) {
currentFact *= i; // i! = (i-1)! * i
sum += currentFact;
}
return sum;
}
i=1: currentFact = 1*1 = 1! = 1 sum = 1 i=2: currentFact = 1*2 = 2! = 2 sum = 1+2 = 3 i=3: currentFact = 2*3 = 3! = 6 sum = 3+6 = 9 i=4: currentFact = 6*4 = 4! = 24 sum = 9+24 = 33 ... 時間複雜度：O(n) vs O(n²) 空間複雜度：O(1)
| 類型 | 最大可表示階乘 | 近似值 | 位元數 |
|---|---|---|---|
int (32-bit) | 12! | 4.79×10⁸ | 31 bits |
long long (64-bit) | 20! | 2.43×10¹⁸ | 63 bits |
double | 170! | 7.26×10³⁰⁶ | 53 bits 精度 |
long double (80-bit) | 1754! | ~10⁴⁹³² | 64 bits 精度 |
// 陣列模擬大整數乘法（十進制每位一個元素）
#define MAX_DIGITS 10000
void multiplyBigInt(int *digits, int *len, int multiplier) {
int carry = 0;
for (int i = 0; i < *len; i++) {
int prod = digits[i] * multiplier + carry;
digits[i] = prod % 10;
carry = prod / 10;
}
while (carry > 0) {
digits[(*len)++] = carry % 10;
carry /= 10;
}
}
void printBigInt(int *digits, int len) {
for (int i = len - 1; i >= 0; i--) putchar('0' + digits[i]);
putchar('\n');
}
void bigFactorial(int n) {
int digits[MAX_DIGITS] = {1};
int len = 1;
for (int i = 2; i <= n; i++) {
multiplyBigInt(digits, &len, i);
}
printBigInt(digits, len);
}
// 使用範例：計算 100!
// bigFactorial(100); // 輸出 158 位數字
n! ≈ √(2πn) (n/e)ⁿ，用於估算大數階乘數量級。eˣ = Σ xⁿ/n!、sin x = Σ (-1)ⁿ x²ⁿ⁺¹/(2n+1)! 等數值計算基礎。Γ(n) = (n-1)!，將階乘擴展至複數域。階乘計算是理解遞迴、迭代、動態規劃（自底向上）、大數運算、數值分析的絕佳切入點。建議從單迴圈優化版著手，體會「狀態保留與重用」的動態規劃核心思想，再嘗試實作任意精度版本，打通從基礎語法到演算法工程的完整鏈路。
