萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 階乘函數實作:迴圈法與遞迴法完整比較與效能分析

階乘定義

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

尾遞迴優化(PHP 不支援,但可手動轉迴圈)

// 尾遞迴形式(編譯器若支援可優化為迴圈)
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";
}

實際應用場景

  • 排列組合計算:C(n,k) = n! / (k!(n-k)!)
  • 機率統計:泊松分佈、二項分佈
  • 演算法複雜度分析
  • 密碼學:某些素數測試

組合數高效計算(避免巨大階乘中間值)

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);  // 直接計算,不溢位(浮點數)
copyright © 萬盛學電腦網 all rights reserved