php recursion,PHP与Recursion 学习笔记_weixin_39520393的博客-程序员宝宝

技术标签: php recursion  

在程序设计中,递归(Recursion)是一个很常见的概念,合理使用递归,可以提升代码的可读性,但同时也可能会带来一些问题。

下面以阶乘(Factorial)为例来说明一下递归的用法,实现语言是PHP:

function factorial($n) {

if ($n == 0) {

return 1;

}

return factorial($n - 1) * $n;

}

var_dump(factorial(100));

?>

如果安装了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来实现一个尾调用版本的阶乘:

function factorial($n, $accumulator = 1) {

if ($n == 0) {

return $accumulator;

}

return factorial($n - 1, $accumulator * $n);

}

var_dump(factorial(100));

?>

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

function factorial($n, $accumulator = 1) {

if ($n == 0) {

return $accumulator;

}

return function() use($n, $accumulator) {

return factorial($n - 1, $accumulator * $n);

};

}

function trampoline($callback, $params) {

$result = call_user_func_array($callback, $params);

while (is_callable($result)) {

$result = $result();

}

return $result;

}

var_dump(trampoline('factorial', array(100)));

?>

看上去不错,不过我不得不向大家道个歉,本文用递归实现阶乘其实是个玩笑,实际上只要用一个循环就行了,《代码大全》里专门提到了这一点:

function factorial($n) {

$result = 1;

for ($i = 1; $i <= $n; $i++) {

$result *= $i;

}

return $result;

}

var_dump(factorial(100));

?>

还有很多别的方法可以用来规避递归引起的栈溢出问题,比如说Python中可以通过装饰器和异常来消灭尾调用,让人有一种别有洞天的感觉:

Tail Call Optimization Decorator (Python recipe)

另外,Python之父关于为何不在Python中支持尾调用的博文也很有看头:

Tail Recursion Elimination

Final Words on Tail Calls

好了,就写到这吧。除非能提升代码可读性,否则没有必要使用递归;迫不得已之时,最好考虑使用Tail Call或Trampoline等技术来规避潜在的栈溢出问题。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_39520393/article/details/115231712

智能推荐

数组的使用_一个虽然帅,但是菜的cxy的博客-程序员宝宝

一:数组的介绍数组是一种数据结构,它可以存储多个数据,一个数据就是一个元素,通常可以通过元素的下标来访问元素和为元素赋值!一个数组中,只能存储一种数据类型的数据二:数组的创建方式2.1:静态初始化:由程序员显示的指定每个元素的初始值,由系统决定长度int[] arr = new int[]{1,2,3};int[] arr = {1,2,3}; //简化形式: 推荐2.2:动态初...

Javascript概述_verphan的博客-程序员宝宝

是的, 我就是鼎鼎大名的Javascript, 典型的高富帅,前端编程之王,数以百万计的程序员使用我来编程。 如果你没有用过我就太out了。 不过当我是一个屌丝时, 真的没有想到能发展到如今的地位…… 第一章:出世我出生在上古时代的浏览器Netscape中, 那个时候的网页真是乏善可陈, 你可能都想象不到, 主要是些丑陋的静态文本和简单的图片, 和现在美轮美奂的页面相比,差的实在太远了, 不信你

176. 第二高的薪水(mysql 简单题)_LL褚的博客-程序员宝宝_第二高的薪水

题目编写一个 SQL 查询,获取 Employee 表中第二高的薪水(Salary) 。+----+--------+| Id | Salary |+----+--------+| 1 | 100 || 2 | 200 || 3 | 300 |+----+--------+例如上述 Employee 表,SQL查询应该返回 200 作为第二高的薪水。如果不存在第二高的薪水,那么查询应返回 null。+---------------------+| Second

JSON三种创建方式_艾伦蓝的博客-程序员宝宝

第一种var myObject = { "name1":"ddA", "name2":"Add" }; 第二种var Animals = new Object(); Animals.name = "dog";Animals.sex = "Male";Animals.age = "2";第三种function Man() {

Net学习日记_ASP.Net_HTTP协议_weixin_30235225的博客-程序员宝宝

转载于:https://www.cnblogs.com/lisong-home/p/7889947.html

随便推点

IOS9获取HTML数据报错解决_qqyadf的博客-程序员宝宝

NSURL *url = [NSURLURLWithString:urlPath];NSError *error = [[NSErroralloc]init];[NSStringstringWithContentsOfURL:url encoding:NSUTF8StringEncodingerror:&error]error返回错误信息:Error Dom

浅谈几种基本的点估计方法及实例_止于至玄的博客-程序员宝宝_点估计应用案例

参数估计有两种形式:点估计与区间估计。本文选择几种常用的点估计方法作一些讨论。用于估计未知参数的统计量称为点估计(量)。参数 θθ\theta 的估计量常用 θ^=θ^(x1,x2,…,xn)θ^=θ^(x1,x2,…,xn)\hat{\theta} = \hat{\theta}(x_{1},x_{2}, \dots, x_{n}) 表示,参数 θθ\theta 的可能取值范围称为参数空间,记...

Vue first project_weixin_40728070的博客-程序员宝宝

cmd 中输入vue create 项目名,创建一个项目(你要在哪个目录下创建,先跳到该目录,要不然直接在c/dht/下)。用vscode开发安装 npm, eslient(代码格式化), vetur插件。根目录下各文件的作用node_modules:用项目开发用的依赖public:下index.html网页入口src:下assets 图片等资源 components 组件默认有一个组件App.vue 所有页面的入口因为程序是单页面,从这里进入所有页面main.j...

一篇文章带你搞定 SpringBoot 中拦截器的使用_南淮北安的博客-程序员宝宝

文章目录一、问题引入二、SpringBoot 中的拦截器的实现一、问题引入前面已经学习过SpringMVC 中的拦截器:一篇文章带你搞定 SpringMVC 中的拦截器本文主要实现对于 SpringBoot 中的拦截器的实现二、SpringBoot 中的拦截器的实现(1)自定义拦截器 MyInterceptor/** * 自定义拦截器 */@Componentpublic class MyInterceptor implements HandlerInterceptor { /

emulator: ERROR: x86 emulation currently requires hardware acceleration!Please ensure Intel HAXM is_happyrabbit456的博客-程序员宝宝

Android Studio 1.0 已经放出来了,以后的Android平台开发激昂逐步从Eclipse向Android Studio迁移,为了能不落伍我也特意从Google下载了Android Studio的安装包,并且兴高采烈地创建了我的第一个android项目。但是当运行的时候就他么悲催了。emulator: ERROR: x86 emulation currently requ

文件上传插件 ueditor 独立上传功能_weixin_34187822的博客-程序员宝宝

为什么80%的码农都做不了架构师?&gt;&gt;&gt; ...