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中可以通过装饰器来消灭尾调用,让人有一种别有洞天的感觉:
另外,Python之父关于为何不在Python中支持尾调用的博文也很有看头:
除非能提升代码可读性,否则没有必要使用递归;迫不得已之时,最好考虑使用Tail Call或Trampoline等技术来规避潜在的栈溢出问题。
建议继续学习:
- 循环、迭代、遍历和递归 (阅读:4432)
- 递归并不一定非得是“自己调用自己的function” (阅读:3166)
- 小心递归次数限制 (阅读:3070)
- PHP正则之递归匹配 (阅读:2705)
- 倒置字符串中的单词 (阅读:2463)
- 无限递归导致 Segmentation fault (阅读:2420)
- 递归创建目录的一个函数 (阅读:2087)
- 递归字符转义 (阅读:1961)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:老王 来源: 火丁笔记
- 标签: Recursion 递归
- 发布时间:2012-07-30 23:58:01
- [66] Go Reflect 性能
- [65] Oracle MTS模式下 进程地址与会话信
- [64] 如何拿下简短的域名
- [59] android 开发入门
- [59] IOS安全–浅谈关于IOS加固的几种方法
- [58] 图书馆的世界纪录
- [58] 【社会化设计】自我(self)部分――欢迎区
- [53] 视觉调整-设计师 vs. 逻辑
- [47] 界面设计速成
- [46] 读书笔记-壹百度:百度十年千倍的29条法则