在程序設計中，遞歸（Recursion）是一個很常見的概念，合理使用遞歸，可以提升代碼的可讀性，但同時也可能會帶來一些問題。
下面以階乘（Factorial）為例來說明一下遞歸的用法，實現語言是PHP：
<?php
function factorial($n) {
if ($n == 0) {
return 1;
}
return factorial($n - 1) * $n;
}
var_dump(factorial(100));
?>
如果安裝了XDebug的話，可能會遇到如下錯誤：
Fatal error: Maximum function nesting level of ’100′ reached, aborting!
注：這是XDebug的一個保護機制，可以通過max_nesting_level選項來設置。
即便代碼能正常運行，只要我們不斷增大參數，程序遲早會報錯：
Fatal error: Allowed memory size of … bytes exhausted
為什麼呢？簡單點說就是遞歸造成了棧溢出。有幾個方法可以用來規避這個問題，比如說利用尾調用（Tail Call）來消除遞歸對棧的影響。
下面以Lua作為描述語言來說明尾調用的含義，代碼如下：
function factorial(n)
if (n == 0) then
return 1
end
return factorial(n - 1) * n
end
print(factorial(100))
這段代碼同樣會遇到棧溢出的問題。怎樣利用尾調用來搞定呢？讓我們先來看看尾調用的定義：如果一個函數在執行了一次函數調用後，不再做別的事就稱為尾調用。形象點說就是直接返回一個函數調用。尾調用不會返回原來的函數，所以不需要額外的棧保留調用函數的數據。上面代碼改成尾調用後類似下面代碼的樣子：
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))
注：關於Lua中尾調用的介紹可以參考：Proper Tail Recursion。
照貓畫虎，我們用PHP來實現一個尾調用版本的階乘：
<?php
function factorial($n, $accumulator = 1) {
if ($n == 0) {
return $accumulator;
}
return factorial($n - 1, $accumulator * $n);
}
var_dump(factorial(100));
?>
可惜測試後才發現PHP根本不支持尾調用！好在天無絕人之路，仔細閱讀維基百科中關於尾調用的介紹，你會發現裡面提到了Trampoline的概念。簡單點說就是利用高階函數消除遞歸，依照這樣的理論基礎，我們可以把上面的尾調用代碼改寫成如下方式：
<?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', array(100)));
?>
看上去不錯，不過我不得不向大家道個歉，本文用遞歸實現階乘其實是個玩笑，實際上只要用一個循環就行了，《代碼大全》裡專門提到了這一點：
<?php
function factorial($n) {
$result = 1;
for ($i = 1; $i <= $n; $i++) {
$result *= $i;
}
return $result;
}
var_dump(factorial(100));
?>
還有很多別的方法可以用來規避遞歸引起的棧溢出問題，比如說Python中可以通過裝飾器和異常來消滅尾調用，讓人有一種別有洞天的感覺：
Tail Call Optimization Decorator (Python recipe)
另外，Python之父關於為何不在Python中支持尾調用的博文也很有看頭：
Tail Recursion Elimination
Final Words on Tail Calls
好了，就寫到這吧。除非能提升代碼可讀性，否則沒有必要使用遞歸；迫不得已之時，最好考慮使用Tail Call或Trampoline等技術來規避潛在的棧溢出問題。
