PHP 遞歸與尾調用優化：從階乘看棧溢出解決方案

遞歸的優雅與陷阱

在程式設計中，遞歸能以極簡代碼表達複雜邏輯，提升可讀性。但若不加節制，遞歸深度過大極易導致棧溢出。本文以 PHP 為例，從階乘函數切入，層層剖析遞歸的記憶體模型、尾調用優化（TCO）原理，以及 PHP 不支援 TCO 時的替代方案——Trampoline 技術。

一、朴素遞歸與棧溢出

最直觀的階乘實現：

<?php
function factorial($n) {
    if ($n == 0) return 1;
    return factorial($n - 1) * $n;
}
var_dump(factorial(100));

執行時若啟用 XDebug，會觸發 Maximum function nesting level of '100' reached；即使調大嵌套層級，隨著參數增大，終將拋出 Allowed memory size exhausted。根因在於每次遞歸調用都會在呼叫棧保存上下文（返回地址、區域變量等），棧空間有限，深度遞歸必然耗盡記憶體。

二、尾調用優化（TCO）原理

若函數最後一步僅是返回另一個函數調用，即為尾調用。此時編譯器/解釋器可複用當前棧幀，避免棧增長。以 Lua 為例：

function factorial(n, accumulator)
    accumulator = accumulator or 1
    if (n == 0) then return accumulator end
    return factorial(n - 1, accumulator * n)  -- 尾調用
end
print(factorial(100))

此處 accumulator 累積中間結果，遞歸調用為最後一條指令，Lua 引擎會將其優化為迴圈，常數空間完成計算。

三、PHP 不支援 TCO 的現狀

照搬尾調用寫法到 PHP：

<?php
function factorial($n, $accumulator = 1) {
    if ($n == 0) return $accumulator;
    return factorial($n - 1, $accumulator * $n);  // 仍會棧溢出
}
var_dump(factorial(100));

實測證實 PHP（截至 8.x）未實現 TCO，棧幀依然疊加。這與 Zend Engine 設計有關，社區雖有 RFC 討論但尚未落地。

四、Trampoline：用高階函數消除遞歸

維基百科提出 Trampoline 模式：將遞歸函數改為返回「下一步計算的閉包」，由外部驅動器迭代執行，從而將遞歸轉為迭代。PHP 實現：

<?php
function factorial($n, $accumulator = 1) {
    if ($n == 0) return $accumulator;
    return function() use($n, $accumulator) {
        return factorial($n - 1, $accumulator * $n);
    };
}

function trampoline($callback, $params) {
    $result = call_user_func_array($callback, $params);
    while (is_callable($result)) {
        $result = $result();
    }
    return $result;
}

var_dump(trampoline('factorial', [100]));  // 成功輸出 9.3326215443944E+157

核心思想：factorial 不再直接遞歸，而是返回一個無參閉包；trampoline 在迴圈中不斷調用閉包，直到得到最終值。此過程僅佔用常數棧空間，完美規避溢出。

五、工程實踐：循環才是正解

《代碼大全》明確指出：階乘等線性遞歸問題，迭代方案更優。PHP 中：

<?php
function factorial($n) {
    $result = 1;
    for ($i = 1; $i <= $n; $i++) $result *= $i;
    return $result;
}
var_dump(factorial(100));

無棧溢出風險、效率最高、可讀性不減。除非遞歸能顯著簡化邏輯（如樹遍歷、分治演算法），否則優先選擇迭代。

六、跨語言視角

• Python：Guido van Rossum 明確反對 TCO，但可用裝飾器+異常模擬尾調用消除。
• Scheme/JavaScript (ES6)：語言規範要求實現 TCO，遞歸安全可靠。
• JVM/.NET：JIT 編譯器可在運行時識別並優化尾調用。

總結

1. 遞歸雖美，棧溢出是硬傷；PHP 無原生 TCO 支援。
2. Trampoline 以高階函數將遞歸轉迭代，是 PHP 環境下的通用逃生方案。
3. 工程上能用 for/while 解決的，堅決不用遞歸；必須遞歸時，評估深度並考慮 Trampoline 或顯式棧模擬。