|
不同的語(yǔ)言對(duì)尾遞歸的支持都有所不同，編譯器的優(yōu)化也不盡相同。我們之前看了C語(yǔ)言的尾遞歸，那么在PHP里又是如何的呢？
PHP對(duì)尾遞歸沒(méi)有優(yōu)化效果
先來(lái)看下實(shí)驗(yàn)。
07 | return factorial($n-1) * $n; |
10 | var_dump(factorial(100)); |
如果安裝了XDebug的話，可能會(huì)遇到如下錯(cuò)誤：
1 | Fatal error: Maximum function nesting level of '100' reached, aborting! |
這是XDebug的一個(gè)保護(hù)機(jī)制，可以通過(guò)max_nesting_level選項(xiàng)來(lái)設(shè)置。放開(kāi)設(shè)置的話，程序還是能夠正常運(yùn)行的。
即便代碼能正常運(yùn)行，只要我們不斷增大參數(shù)，程序遲早會(huì)報(bào)錯(cuò)：
1 | Fatal error: Allowed memory size of … bytes exhausted |
為什么呢？簡(jiǎn)單點(diǎn)說(shuō)就是遞歸造成了棧溢出。按照之前的思路，我們可以試下用尾遞歸來(lái)消除遞歸對(duì)棧的影響，提高程序的效率。
02 | function factorial($n, $acc) |
07 | return factorial($n-1, $acc * $n); |
11 | var_dump(factorial(100, 1)); |
XDebug同樣報(bào)錯(cuò)，并且程序的執(zhí)行時(shí)間并沒(méi)有明顯變化。
1 | Fatal error: Maximum function nesting level of '100' reached, aborting! |
事實(shí)證明，尾遞歸在php中是沒(méi)有任何優(yōu)化效果的。
PHP如何消除遞歸
先看看下面的源代碼：
02 | function factorial($n, $accumulator = 1) { |
07 | return function() use($n, $accumulator) { |
08 | return factorial($n - 1, $accumulator * $n); |
12 | function trampoline($callback, $params) { |
13 | $result = call_user_func_array($callback, $params); |
15 | while (is_callable($result)) { |
22 | var_dump(trampoline('factorial', array(100))); |
現(xiàn)在XDebug不再警報(bào)效率問(wèn)題了。
注意到trampoline()函數(shù)沒(méi)？簡(jiǎn)單點(diǎn)說(shuō)就是利用高階函數(shù)消除遞歸。想更進(jìn)一步了解 call_user_func_array，可以參看這篇文章：PHP函數(shù)補(bǔ)完：call_user_func()與call_user_func_array()
還有很多別的方法可以用來(lái)規(guī)避遞歸引起的棧溢出問(wèn)題，比如說(shuō)Python中可以通過(guò)裝飾器和異常來(lái)消滅尾調(diào)用，讓人有一種別有洞天的感覺(jué)。
小結(jié)
在C中的尾遞歸優(yōu)化是gcc編譯器做的。一般的線性遞歸修改成為尾遞歸最大的優(yōu)勢(shì)在于減少了遞歸調(diào)用棧的開(kāi)銷。從php那個(gè)例子就明顯看出來(lái)遞歸開(kāi)銷對(duì)程序的影響。但是并不是所有語(yǔ)言都支持尾遞歸的，即使支持尾遞歸的語(yǔ)言也一般是在編譯階段對(duì)尾遞歸進(jìn)行優(yōu)化，比如C語(yǔ)言對(duì)尾遞歸的優(yōu)化。在使用尾遞歸對(duì)代碼進(jìn)行優(yōu)化的時(shí)候，必須先了解這門(mén)語(yǔ)言對(duì)尾遞歸的支持。
在PHP里，除非能提升代碼可讀性，否則沒(méi)有必要使用遞歸；迫不得已之時(shí)，最好考慮使用Tail Call或Trampoline等技術(shù)來(lái)規(guī)避潛在的棧溢出問(wèn)題。
|
