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