您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 相關知識

PHP 遞歸函數三大實現模式與數字累加實戰詳解

編輯：PHP 相關知識

PHP 遞歸函數三大實現模式與數字累加實戰詳解

遞歸是程式設計中「函數調用自身」的強大技術，適用於樹狀結構遍歷、數學運算、分治算法等場景。關鍵在於終止條件與狀態傳遞。本文深度解析 PHP 中三種主流遞歸實現模式，並以「1 到 N 累加」為例演示最佳實踐。

核心原理：調用棧與狀態保持

每次遞歸調用都會在內存棧中創建新的幀，包含局部變量、參數、返回地址。若無終止條件，棧溢出導致「Allowed memory size exhausted」。狀態在層層調用間傳遞的三大機制如下：

模式一：引用參數傳遞（&$ref）

利用 PHP 引用機制，讓多層調用共享同一變量內存地址。

<?php
function sumRef($n, &$result = 0) {
    if ($n <= 0) return $result;
    $result += $n;
    return sumRef($n - 1, $result);
}

echo sumRef(10); // 55
?>

特點：無需全局污染，性能優，參數明確。注意：PHP 5.4+ 建議在函數定義時聲明引用，調用時不需加 `&`。

模式二：全局變量（$GLOBALS / global）

將狀態提升至全局符號表，跨作用域可見。

<?php
$GLOBALS['sum'] = 0;
function sumGlobal($n) {
    if ($n <= 0) return $GLOBALS['sum'];
    $GLOBALS['sum'] += $n;
    sumGlobal($n - 1);
}

sumGlobal(10);
echo $GLOBALS['sum']; // 55
?>

缺點：破壞封裝性，併發/多線程環境下極不安全，難以單元測試，不推薦生產環境使用。

模式三：靜態變量（static）

靜態變量僅在首次調用時初始化，生命周期贯穿整個腳本執行期，天然適合遞歸狀態保持。

<?php
function sumStatic($n) {
    static $result = 0; // 僅初始化一次
    if ($n <= 0) {
        $ret = $result;
        $result = 0; // 重置供下次調用
        return $ret;
    }
    $result += $n;
    sumStatic($n - 1);
}

echo sumStatic(10); // 55
echo sumStatic(5);  // 15 (獨立計算)
?>

優勢：封裝性好、無全局污染、語義清晰。注意：需手動重置，否則二次調用會累加上次結果。

進階：尾遞歸優化與返回值傳遞

PHP 不支援尾調用優化（TCO），但可通過「返回值攜帶狀態」避免外部變量：

<?php
// 純函數式寫法：返回值層層回傳
function sumPure($n, $acc = 0) {
    return $n <= 0 ? $acc : sumPure($n - 1, $acc + $n);
}

echo sumPure(10); // 55
?>

此模式無副作用、可測試、易並行，是現代 PHP 開發首選。

實戰案例：數字累加的多種姿勢

1. 經典遞歸（教科書式）

function summation($n) {
    return $n == 0 ? 0 : $n + summation($n - 1);
}

缺點：棧深度 O(n)，n > 10^4 易溢出。

2. 迭代替代（生產環境推薦）

function sumIter($n) {
    $sum = 0;
    for ($i = 1; $i <= $n; $i++) $sum += $i;
    return $sum;
}
// 或 數學公式 O(1)
function sumMath($n) {
    return $n * ($n + 1) / 2;
}

3. 生成器實現惰性求和（PHP 5.5+）

function nums($n) {
    for ($i = 1; $i <= $n; $i++) yield $i;
}
echo array_sum(iterator_to_array(nums(10))); // 55

遞歸陷阱與最佳實踐

陷阱	後果	對策
缺少/錯誤終止條件	無限遞歸 → 棧溢出致命錯誤	嚴格定義 base case，邊界測試
大數據量深度遞歸	超出 memory_limit / xdebug.max_nesting_level	改用迭代、生成器、或增加配置
重複計算（如斐波那契）	指數級時間複雜度	記憶化、動態規劃、尾遞歸
靜態變量未重置	多次調用結果錯誤	函數入口/出口顯式重置