PHP 遞歸算法完全指南：原理、實現模式、經典案例與效能優化

什麼是遞歸？

遞歸是指函數直接或間接調用自身來解決問題的編程技巧。核心思想：將大問題分解為結構相同的子問題，直到達到可直接解決的基準情況。

遞歸的兩大必要條件

1. 遞歸關係：問題可分解為同類子問題（如 f(n) = f(n-1) + n）
2. 終止條件：存在不再遞歸的基準情況（如 f(1) = 1），否則導致無限遞歸 → 棧溢出

調用棧機制圖解

主程式: factorial(3)
  → factorial(3) 調用 factorial(2)  [棧幀1: 等待 2! 結果]
    → factorial(2) 調用 factorial(1)  [棧幀2: 等待 1! 結果]
      → factorial(1) 調用 factorial(0)  [棧幀3: 等待 0! 結果]
        → factorial(0) 返回 1 (基準情況)
      ← factorial(1) 計算 1*1=1 返回
    ← factorial(2) 計算 2*1=2 返回
  ← factorial(3) 計算 3*2=6 返回
主程式獲得結果 6

每次遞歸調用都會在記憶體中建立獨立的棧幀，包含區域變數、參數、返回地址。深度過大會耗盡棧空間。

經典案例 1：階乘

<?php
function factorial(int $n): int {
    // 終止條件
    if ($n <= 1) return 1;
    // 遞歸關係
    return $n * factorial($n - 1);
}

echo factorial(5); // 120
?>

經典案例 2：斐波那契數列（雙遞歸）

<?php
// 朴素遞歸：指數級複雜度 O(2^n)，極度低效
function fibNaive(int $n): int {
    if ($n <= 1) return $n;
    return fibNaive($n-1) + fibNaive($n-2);
}

// 優化 1：記憶化遞歸（自頂向下 DP）O(n)
function fibMemo(int $n, array &$memo = []): int {
    if ($n <= 1) return $n;
    if (isset($memo[$n])) return $memo[$n];
    return $memo[$n] = fibMemo($n-1, $memo) + fibMemo($n-2, $memo);
}

// 優化 2：尾遞歸（需語言支援尾調用優化，PHP 不支援，僅作教學）
function fibTail(int $n, int $a = 0, int $b = 1): int {
    if ($n === 0) return $a;
    return fibTail($n - 1, $b, $a + $b);
}

// 優化 3：迭代法（推薦生產環境）O(n) 時間，O(1) 空間
function fibIter(int $n): int {
    $a = 0; $b = 1;
    for ($i = 0; $i < $n; $i++) {
        [$a, $b] = [$b, $a + $b];
    }
    return $a;
}
?>

經典案例 3：二叉樹中序遍歷

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

// 遞歸版：簡潔優雅
function inorderRecursive(TreeNode $root): array {
    if (!$root) return [];
    return array_merge(
        inorderRecursive($root->left),
        [$root->val],
        inorderRecursive($root->right)
    );
}

// 迭代版（顯式棧）：避免深度過大導致棧溢出
function inorderIterative(TreeNode $root): array {
    $result = [];
    $stack = [];
    $curr = $root;
    while ($curr || $stack) {
        while ($curr) {
            $stack[] = $curr;
            $curr = $curr->left;
        }
        $curr = array_pop($stack);
        $result[] = $curr->val;
        $curr = $curr->right;
    }
    return $result;
}
?>

經典案例 4：目錄遞歸掃描（實戰高頻）

<?php
function scanDirRecursive(string $dir, array &$files = [], int $depth = 0): array {
    $items = scandir($dir);
    foreach ($items as $item) {
        if ($item === '.' || $item === '..') continue;
        $path = $dir . DIRECTORY_SEPARATOR . $item;
        if (is_dir($path)) {
            scanDirRecursive($path, $files, $depth + 1);
        } else {
            $files[] = ['path' => $path, 'depth' => $depth, 'name' => $item];
        }
    }
    return $files;
}

// 使用生成器優化記憶體（PHP 5.5+）
function scanDirGenerator(string $dir): Generator {
    $items = scandir($dir);
    foreach ($items as $item) {
        if ($item === '.' || $item === '..') continue;
        $path = $dir . DIRECTORY_SEPARATOR . $item;
        if (is_dir($path)) {
            yield from scanDirGenerator($path);
        } else {
            yield $path;
        }
    }
}

// 使用
foreach (scanDirGenerator('/var/www') as $file) {
    echo $file . PHP_EOL;
}
?>

遞歸 vs 迭代：效能對比

PHP 遞歸限制與優化策略

1. xdebug.max_nesting_level：預設 256，可在 php.ini 調大（如 1000），但非根治。
2. 尾調用優化 (TCO)：PHP 不支援。尾遞歸仍會增長棧。
3. 記憶化：對重疊子問題（如 Fib、編輯距離）顯著提速。
4. 轉換為迭代/生成器：深度不可控場景（目錄掃描、大樹遍歷）必須轉迭代。
5. 增加棧大小：ulimit -s unlimited (Linux) 或調整 Apache/NGINX 執行緒棧大小，治標不治本。

何時選擇遞歸？決策流程圖

問題是否天然適合分治/樹結構？
  ├─ 是 → 深度是否可控（< 1000）？
  │       ├─ 是 → 遞歸碼更簡潔 → 用遞歸 (+記憶化)
  │       └─ 否 → 必須用迭代/生成器/顯式棧
  └─ 否 → 能否用簡單循環解決？
          ├─ 是 → 用迭代
          └─ 否 → 考慮動態規劃/貪心/圖算法

總結

遞歸是解決自我相似結構問題的利器（樹、圖、分治、回溯）。PHP 中編寫遞歸時必須警惕棧溢出與重複計算。掌握記憶化、生成器、顯式棧迭代三大優化手段，能在保持代碼優雅的同時兼顧效能與穩定性。實戰原則：可讀性優先，效能受限時再重構為迭代。