在程序設(shè)計(jì)中，遞歸(Recursion)是一個(gè)很常見的概念，合理使用遞歸，可以提升代碼的可讀性，但同時(shí)也可能會(huì)帶來(lái)一些問題。

下面以階乘(Factorial)為例來(lái)說明一下遞歸的用法，實(shí)現(xiàn)語(yǔ)言是PHP：

function factorial($n) {

if ($n == 0) {

return 1;

}

return factorial($n - 1) * $n;

}

var_dump(factorial(100));

?>

如果安裝了XDebug的話，可能會(huì)遇到如下錯(cuò)誤：

Fatal error: Maximum function nesting level of ‘100’ reached, aborting!

注：這是XDebug的一個(gè)保護(hù)機(jī)制，可以通過max_nesting_level選項(xiàng)來(lái)設(shè)置。

即便代碼能正常運(yùn)行，只要我們不斷增大參數(shù)，程序遲早會(huì)報(bào)錯(cuò)：

Fatal error: ?Allowed memory size of … bytes exhausted

為什么呢？簡(jiǎn)單點(diǎn)說就是遞歸造成了棧溢出。有幾個(gè)方法可以用來(lái)規(guī)避這個(gè)問題，比如說利用尾調(diào)用(Tail Call)來(lái)消除遞歸對(duì)棧的影響。

下面以Lua作為描述語(yǔ)言來(lái)說明尾調(diào)用的含義，代碼如下：

function factorial(n)

if (n == 0) then

return 1

end

return factorial(n - 1) * n

end

print(factorial(100))

這段代碼同樣會(huì)遇到棧溢出的問題。怎樣利用尾調(diào)用來(lái)搞定呢？讓我們先來(lái)看看尾調(diào)用的定義：如果一個(gè)函數(shù)在執(zhí)行了一次函數(shù)調(diào)用后，不再做別的事就稱為尾調(diào)用。形象點(diǎn)說就是直接返回一個(gè)函數(shù)調(diào)用。尾調(diào)用不會(huì)返回原來(lái)的函數(shù)，所以不需要額外的棧保留調(diào)用函數(shù)的數(shù)據(jù)。上面代碼改成尾調(diào)用后類似下面代碼的樣子：

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))

注：關(guān)于Lua中尾調(diào)用的介紹可以參考：Proper Tail Recursion。

照貓畫虎，我們用PHP來(lái)實(shí)現(xiàn)一個(gè)尾調(diào)用版本的階乘：

function factorial($n, $accumulator = 1) {

if ($n == 0) {

return $accumulator;

}

return factorial($n - 1, $accumulator * $n);

}

var_dump(factorial(100));

?>

可惜測(cè)試后才發(fā)現(xiàn)PHP根本不支持尾調(diào)用！好在天無(wú)絕人之路，仔細(xì)閱讀維基百科中關(guān)于尾調(diào)用的介紹，你會(huì)發(fā)現(xiàn)里面提到了Trampoline的概念。簡(jiǎn)單點(diǎn)說就是利用高階函數(shù)消除遞歸，依照這樣的理論基礎(chǔ)，我們可以把上面的尾調(diào)用代碼改寫成如下方式：

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)));

?>

看上去不錯(cuò)，不過我不得不向大家道個(gè)歉，本文用遞歸實(shí)現(xiàn)階乘其實(shí)是個(gè)玩笑，實(shí)際上只要用一個(gè)循環(huán)就行了，《代碼大全》里專門提到了這一點(diǎn)：

function factorial($n) {

$result = 1;

for ($i = 1; $i <= $n; $i++) {

$result *= $i;

}

return $result;

}

var_dump(factorial(100));

?>

還有很多別的方法可以用來(lái)規(guī)避遞歸引起的棧溢出問題，比如說Python中可以通過裝飾器和異常來(lái)消滅尾調(diào)用，讓人有一種別有洞天的感覺：

Tail Call Optimization Decorator (Python recipe)

另外，Python之父關(guān)于為何不在Python中支持尾調(diào)用的博文也很有看頭：

Tail Recursion Elimination

Final Words on Tail Calls

好了，就寫到這吧。除非能提升代碼可讀性，否則沒有必要使用遞歸；迫不得已之時(shí)，最好考慮使用Tail Call或Trampoline等技術(shù)來(lái)規(guī)避潛在的棧溢出問題。

總結(jié)

以上是生活随笔為你收集整理的php recursion,PHP与Recursion 学习笔记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。