手机浏览 RSS 2.0 订阅 膘叔的简单人生 , 腾讯云RDS购买 | 超便宜Qcloud , 注册 | 登陆

优化递归的效率

首页 > PHP >

原文来自博客园,把代码全部翻译成了PHP的,因为这些东西对PHP同样适用。

函数递归调用是很常见的做法,但是它往往是低效的,本文探讨优化递归效率的思路。
1.尾递归转换成迭代
尾递归是一种简单的递归,它可以用迭代来代替 比如 求阶乘函数的递归表达

PHP代码
  1. <?php  
  2. function  f( $n = 0)  
  3. {  
  4.     if($n<=0)return 1;  
  5.     return $n*f($n-1);  
  6. }  
  7. ?>  
可以转换成完全等价的循环迭代
PHP代码
  1. <?php  
  2. function f($n = 0)  
  3. {  
  4.     $r=0;  
  5.     while$n-- > 0)  
  6.         $r *= $n;  
  7.     return $r;  
  8. }  
  9. ?>  

尾递归是最简单的情形,好的编译器甚至可以自动的识别尾递归并把它转换成循环迭代。

2.动态规划

我一直把动态规划看作尾递归的推广(个人观点),在2维或更高的情况下,直接使用递归会造成大量的重复计算,例如在斐波那契数列的递归关系 Fib(n+2)=Fib(n+1)+Fib(n)中 Fib(3)在计算Fib(4)和Fib(5)都会用到 他被重复计算了2遍,当数列长度增大时 这种浪费会变得越来越明显。

动态规划方法将可能需要的结果全部计算出来 并保存 一般来说 动态规划从最小数开始 自底向上计算所有值(因为后面的结果会用到前面的结果) 直到得到的结果中包含了要求的结果。

PHP代码
  1. <?php  
  2. function Fib( $n)  
  3. {  
  4.     if($n==1)return 1;  
  5.     if($n==0)return 0;  
  6.     return Fib($n-1)+Fib($n-2);  
  7. }  
  8.   
  9. //这个函数我没有测试。。。 我是指转换过来后
  10. function Fib( $n )  
  11. {  
  12.     $f[1]=1;$f[0]=0;  
  13.     for($i=0;$i<=$n;$i++);  
  14.         f[$i]=f[$i-1]+f[$i-2];    
  15.     $r$f[$n];  
  16.     return $r;  
  17. }  
  18.   
  19. ?>  

 

动态规划不会造成重复运算 但是 它可能计算不需要的结果 例如关系式
     a(n)=a(n-2)+a(n-4);
使用动态规划会计算很多不需要的结果,尽管如此,它的效率远远高于直接递归运算。

实际上,大部分时候动态规划把指数级时间复杂度的递归运算变成了多项式级时间复杂度的递推。

3.备忘录

减少重复值的另一个方法是使用备忘录,每次成功计算一个结果 ,就将它存入备忘录中,当再次遇到此问题时,无需重复计算,直接取出即可。

备忘录方法和直接递归相似,只是在函数在计算之前先访问备忘录,如果在备忘录中找到,就无须再计算,直接返回。

备忘录结构可以使用关联数组 哈希表等实现,特别地,当递归参数是整数时 直接用数组就可以了。

与动态规划相比,备忘录消耗了额外的备忘录查找时间,并且和直接递归一样 有大量的多余函数调用开销,但它不会造成额外计算。

4.内联

这是来自Efficient C++的方法,C++编译器不会把递归函数内联,这样,函数调用的开销变得很大。为了提高效率,必须手动内联函数。
递归函数无法完全内联,但是我们可以把它展开,这是前面Fibnacci函数的一层展开

PHP代码
  1. <?php  
  2. function Fib( $n)  
  3. {  
  4.     if($n==1)return 1;  
  5.     if($n==0)return 0;  
  6.   
  7.     $fn1 = $fn2 = 0;  
  8.     if$n-1==1)$fn1=1;  
  9.     else if($n-1==0)$fn1=0;  
  10.     else $fn1=Fib($n-2)+Fib($n-3);  
  11.   
  12.     if($n-2==1)$fn2=1;  
  13.     else if($n-2==0)$fn2=0;  
  14.     else $fn2=Fib($n-3)+Fib($n-4);  
  15.   
  16.     return $fn1+$fn2  
  17. }  
  18.       
  19. ?>  

 5.解递归
尽管我们倾向于虐待计算机 让它帮我们处理较复杂的问题,但是很多时候我们需要获得效率,就必须自己动手,其实很多递归式可以手动解出,组合数学为我们提供了不少工具:
     (1)解齐次递归方程

简单的递归方程可以按以下步骤求解:

解Fibonacci函数的递归方程
首先把它转换成下面的式子
这个代数方程被称为递归方程的特征方程,下一步是解特征方程求出它的所有解,对这个例子来说
根据组合数学的结论
再由
F(0)=0和F(1)=1可以得出方程组
解这个方程组可得到a和b的值
代入前面的公式可以求出Fibnacci通项公式
验证后可以知道,这个公式是正确的,显然用此公式做浮点运算,比使用递归方式快得多。
 (2)母函数
 
组合数学中还提供了一种更强有力的处理手段:生成函数(又称为母函数)
仍然以求解Fibonacci数列为例,为了易于理解,我这里把生成函数描述成一个以Fibonacci数列为系数的多项式。即
现在考虑这样一个多项式
按g(x)的定义,可以这样展开
这个时候不要忘记我们的递推公式,可以进一步化简为
这个式子与g(x)非常像,将它两边同时乘以x
再整理一下等式
利用F(0)=0,F(1)=1可以求出
这样 我们求出了g(x),等等,g(x)是什么来着?不是以Fibonacci数列为系数的多项式么?现在求出的东西是什么?不要急,用泰勒级数展开就能得到通项公式了,结果跟上面的是一样的。(太麻烦了,略过略过^_^)

原文地址:http://www.cnblogs.com/winter-cn/archive/2008/08/23/1274475.html
由于部分是图片,我就不转换了,而且这些也是公式,没啥好转换的。。。



本站采用创作共享版权协议, 要求署名、非商业和保持一致. 本站欢迎任何非商业应用的转载, 但须注明出自"膘叔", 保留原始链接, 此外还必须标注原文标题和链接.

Tags: php, 递归, 效率, 优化

« 上一篇 | 下一篇 »

只显示10条记录相关文章

使用PHP得到所有的HTTP请求头 (浏览: 47074, 评论: 3)
我为什么会选用phpstorm (浏览: 42408, 评论: 5)
通过file_get_contents来Post数据的实例 (浏览: 35067, 评论: 5)
PHP导入导出Excel方法 (浏览: 34469, 评论: 3)
快速生成目录树 (浏览: 31627, 评论: 7)
PHP中Eval的作用 (浏览: 30228, 评论: 4)
PHP的XSS攻击过滤函数 (浏览: 29716, 评论: 2)
PHP常见错误(二) (浏览: 28483, 评论: 1)
PHP sendmail (浏览: 28401, 评论: 7)
几个ZendStudio使用教程 (浏览: 26413, 评论: 0)

1条记录访客评论

你关于尾递归的举例是不正确的,例子中那个不是尾递归,尾递归在编译器做过优化的情况下即便输入不穷大都不会造成stackoverflow.

Post by peter on 2012, June 1, 6:25 PM 引用此文发表评论 #1


发表评论

评论内容 (必填):