PHP 遞歸算法原理與實戰應用詳解

什麼是遞歸？

遞歸是指函式在定義中直接或間接呼叫自身的程式設計技巧。就像生活中的「套娃」：打開一個娃娃，裡面還有一個更小的，直到最小的那個無法再打開為止。

經典範例：階乘計算

數學定義：n! = n × (n-1)!，且 0! = 1（終止條件）。

錯誤寫法（無終止條件 → 無限遞歸）

function factorial($i) {
    return factorial($i - 1) * $i; // 會一直呼叫到負無窮
}

正確寫法

function factorial($i) {
    if ($i > 0) {
        return factorial($i - 1) * $i;
    }
    return 1; // 基準情況
}

// 執行 factorial(3) 過程：
// factorial(3) → 3 * factorial(2)
//              → 3 * (2 * factorial(1))
//              → 3 * (2 * (1 * factorial(0)))
//              → 3 * (2 * (1 * 1)) = 6

遞歸適用的兩個條件

1. 問題可分解為相同性質的子問題（如 s(n) = s(n-1) + n）
2. 存在明確的終止條件（如 s(1) = 1）

範例：1 到 n 累加

function progression($n) {
    if ($n == 1) return 1;
    return progression($n - 1) + $n;
}
echo progression(100); // 5050

實際應用：二元樹中序遍歷

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val) { $this->val = $val; }
}

function inorder($node) {
    if ($node) {
        inorder($node->left);
        echo $node->val . ' ';
        inorder($node->right);
    }
}

// 建構樹：    1
//           / \
//          2   3
//         / \
//        4   5
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
$root->left->left = new TreeNode(4);
$root->left->right = new TreeNode(5);

inorder($root); // 輸出：4 2 5 1 3

效能提醒

每次遞歸呼叫都會產生新的堆疊幀，深度過大可能導致堆疊溢位。PHP 預設記憶體限制較低，處理大規模資料時建議改用迴圈或尾遞歸優化（PHP 尚不原生支援，需手動轉換）。