PHP 遞歸與遞推思想詳解：以求和函數為例

核心概念

• 遞歸：函數直接或間接調用自身，將問題分解為同類子問題，需有**基線條件**終止。
• 遞推：從基線條件出發，逐步推導至目標問題，通常用循環實現（自底向上）。

經典例子：1+2+...+n

遞歸實現

function sum($n) {
    if ($n == 1) return 1;          // 基線條件
    return $n + sum($n - 1);        // 遞歸調用
}

執行流程：sum(5) → 5 + sum(4) → 5 + 4 + sum(3) ... → 5+4+3+2+1。調用棧深度 O(n)，大 n 時可能棧溢出。

遞推實現

function sum($n) {
    $result = 0;
    for ($i = 1; $i <= $n; $i++) {
        $result += $i;              // 逐步累加
    }
    return $result;
}

無調用棧開銷，時間 O(n)，空間 O(1)。

數學歸納法對應

1. 驗證 n=1 成立。
2. 假設 n=k 成立，證明 n=k+1 成立：sum(k+1) = sum(k) + (k+1)。

何時選擇哪種？

PHP 具體注意

• PHP 默認無尾調用優化，深遞歸必爆棧（默認 xdebug.max_nesting_level=256）。
• 大數據量務必改寫為循環或使用生成器 yield 實現惰性遞推。