n! = 1 × 2 × 3 × ... × n,定義 0! = 1
function factorial_iterative($n) {
if ($n < 0) throw new InvalidArgumentException('負數無階乘');
if ($n === 0) return 1;
$result = 1;
for ($i = 2; $i <= $n; $i++) {
$result *= $i;
}
return $result;
}
// 測試
echo factorial_iterative(4); // 24
echo factorial_iterative(0); // 1
function factorial_recursive($n) {
if ($n < 0) throw new InvalidArgumentException('負數無階乘');
if ($n <= 1) return 1; // 0! = 1! = 1
return $n * factorial_recursive($n - 1);
}
// 執行流程:factorial(4)
// 4 * factorial(3)
// 3 * factorial(2)
// 2 * factorial(1)
// 返回 1
// 返回 2
// 返回 6
// 返回 24
| 指標 | 迴圈法 | 遞迴法 |
|---|---|---|
| 時間複雜度 | O(n) | O(n) |
| 空間複雜度 | O(1) | O(n) 呼叫堆疊 |
| 最大安全 n | 受限於整數溢位 | 受限於堆疊深度(~10^4-10^5) |
| PHP 實際限制 | n ≤ 170(float 精度) | n ≤ 10000+(記憶體/堆疊限制) |
<?php
// PHP 整數上限(64位系統:9223372036854775807)
echo PHP_INT_MAX . "\n";
// 階乘快速超過整數範圍
echo factorial_iterative(20); // 2432902008176640000 (超過 64 位)
// 解決方案:使用 BCMath 或 GMP 擴展
function factorial_bcmath($n) {
if ($n < 0) throw new InvalidArgumentException('負數無階乘');
$result = '1';
for ($i = 2; $i <= $n; $i++) {
$result = bcmul($result, (string)$i);
}
return $result;
}
echo factorial_bcmath(100); // 正確輸出 158 位數字
// GMP 更快
function factorial_gmp($n) {
$result = gmp_init(1);
for ($i = 2; $i <= $n; $i++) {
gmp_mul($result, $i);
}
return gmp_strval($result);
}
// 尾遞迴形式(編譯器若支援可優化為迴圈)
function factorial_tail($n, $acc = 1) {
if ($n <= 1) return $acc;
return factorial_tail($n - 1, $n * $acc);
}
// PHP 不做尾呼叫優化,仍會堆疊溢位
// 必須手寫迴圈版本
function factorial_memoized($n) {
static $cache = [0 => 1, 1 => 1];
if ($n < 0) throw new InvalidArgumentException('負數無階乘');
if (isset($cache[$n])) return $cache[$n];
// 遞增建立快取
$last = max(array_keys($cache));
for ($i = $last + 1; $i <= $n; $i++) {
$cache[$i] = $cache[$i - 1] * $i;
}
return $cache[$n];
}
// 連續呼叫極快
for ($i = 0; $i <= 20; $i++) {
echo "$i! = " . factorial_memoized($i) . "\n";
}
function combination($n, $k) {
if ($k < 0 || $k > $n) return 0;
if ($k > $n - $k) $k = $n - $k; // 取較小者
$result = 1;
for ($i = 1; $i <= $k; $i++) {
$result = $result * ($n - $k + $i) / $i;
}
return $result;
}
echo combination(100, 50); // 直接計算,不溢位(浮點數)