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