在程序设计中，递归（recursion）是一个很常见的概念，合理使用递归，可以提升代码的可读性，但同时也可能会带来一些问题。 下面以阶乘（factorial）为例来说明一下递归的用法，实现语言是php： ?phpfunction factorial($n) { if ($n == 0) { return 1; } re
在程序设计中，递归（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) * nendprint(factorial(100))
这段代码同样会遇到栈溢出的问题。怎样利用尾调用来搞定呢？让我们先来看看尾调用的定义：如果一个函数在执行了一次函数调用后，不再做别的事就称为尾调用。形象点说就是直接返回一个函数调用。尾调用不会返回原来的函数，所以不需要额外的栈保留调用函数的数据。上面代码改成尾调用后类似下面代码的样子：
function factorial(n, accumulator) accumulator = accumulator or 1 if (n == 0) then return accumulator end return factorial(n - 1, accumulator * n)endprint(factorial(100))
注：关于lua中尾调用的介绍可以参考：proper tail recursion。
照猫画虎，我们用php来实现一个尾调用版本的阶乘：

可惜测试后才发现php根本不支持尾调用！好在天无绝人之路，仔细阅读维基百科中关于尾调用的介绍，你会发现里面提到了trampoline的概念。简单点说就是利用高阶函数消除递归，依照这样的理论基础，我们可以把上面的尾调用代码改写成如下方式：

看上去不错，不过我不得不向大家道个歉，本文用递归实现阶乘其实是个玩笑，实际上只要用一个循环就行了，《代码大全》里专门提到了这一点：
还有很多别的方法可以用来规避递归引起的栈溢出问题，比如说python中可以通过装饰器和异常来消灭尾调用，让人有一种别有洞天的感觉：
tail call optimization decorator (python recipe)另外，python之父关于为何不在python中支持尾调用的博文也很有看头：
tail recursion eliminationfinal words on tail calls好了，就写到这吧。除非能提升代码可读性，否则没有必要使用递归；迫不得已之时，最好考虑使用tail call或trampoline等技术来规避潜在的栈溢出问题。
原文地址：php与recursion, 感谢原作者分享。