PHP與遞歸Recursion

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

　　下面以階乘(Factorial)為例來說明一下遞歸的用法，實現代碼為PHP：

　　如果安裝了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根本不支持尾調用!不過天無絕人之路，仔細研讀維基百科中關于尾調用的介紹，你會發現里面提到了Trampoline的概念。簡單點說就是利用高階函數消除遞歸，依照這樣的理論基礎，我們可以把上面的尾調用代碼改寫成如下方式：

　　看上去不錯，不過我不得不向大家道個歉，用遞歸實現階乘其實是個玩笑，實際上，無需使用遞歸，只要用一個循環就行了，印象中《代碼大全》里專門提到了這一點：

　　還有很多別的方法可以用來規避遞歸引起的棧溢出問題，比如說Python中可以通過裝飾器來消滅尾調用，讓人有一種別有洞天的感覺：

　　Tail Call Optimization Decorator (Python recipe)

　　另外，Python之父關于為何不在Python中支持尾調用的博文也很有看頭：

　　Tail Recursion Elimination

　　Final Words on Tail Calls

　　除非能提升代碼可讀性，否則沒有必要使用遞歸;迫不得已之時，最好考慮使用Tail Call或Trampoline等技術來規避潛在的棧溢出問題。

原文轉自：http://blogread.cn/it/article/5612