PHP 遞迴函數實現數字累加：經典範例與尾遞迴優化討論

前言

遞迴是函數呼叫自身解決問題的技巧。累加 1 到 N 是遞迴入門經典範例。本文展示基本遞迴、尾遞迴優化概念與 PHP 實際限制。

基本遞迴實作

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

echo summation(10) . "\n"; // 55
?>

執行流程圖解（N=3）

summation(3)
  = 3 + summation(2)
  = 3 + (2 + summation(1))
  = 3 + (2 + (1 + summation(0)))
  = 3 + (2 + (1 + 0))
  = 6

尾遞迴優化（Tail Call Optimization, TCO）

PHP 不支援 TCO，每次遞迴都會新增堆疊幀，大 N 會導致堆疊溢位（Stack Overflow）。

<?php
// 尾遞迴寫法（理論可優化，但 PHP 不支援）
function summationTail(int $n, int $acc = 0): int {
    if ($n <= 0) return $acc;
    return summationTail($n - 1, $acc + $n);
}

// PHP 仍會產生 N 層堆疊
?>

迭代替代方案（推薦生產環境）

<?php
function summationIterative(int $n): int {
    $sum = 0;
    for ($i = 1; $i <= $n; $i++) {
        $sum += $i;
    }
    return $sum;
}

// 或數學公式 O(1)
function summationFormula(int $n): int {
    return $n * ($n + 1) / 2;
}
?>

遞迴深度限制測試

<?php
function testDepth(int $n): int {
    if ($n <= 0) return 0;
    return 1 + testDepth($n - 1);
}

try {
    echo testDepth(10000) . "\n"; // 可能 Segfault 或 Fatal Error: Maximum function nesting level
} catch (\Throwable $e) {
    echo "錯誤: " . $e->getMessage() . "\n";
}

// 可調整 xdebug.max_nesting_level 或 zend.max_nesting_level (PHP 8+)
?>

總結

遞迴適合邏輯天然遞迴的問題（樹遍歷、分治演算法），線性累加請用迭代或公式。PHP 無 TCO，深度遞迴需謹慎或調整 nesting level。希望本文對您的 PHP 程式設計有所幫助。