一个算法设计技巧:递归转化成迭代

 先向师兄道个歉,那么久才写这篇技术文章。

这里我还是把我那天和大家讨论的东西仔细地整理。

一个算法设计技巧:递归转化成迭代。

在某些特定的情况下,递归的效率是非常低的,必须使用迭代来实现。 下面,将通过两个经典的递归例子,来感悟这两种算法设计方法的效率问题。
 
1.计算n的阶乘。 
学过最基本程序设计知识的同学都知道,递归处理。
#include <stdio.h>
#include<stdlib.h>
long fact(int);

int main(void)
{   int n;
    printf(“请输入一个非负整数n:n”);
    scanf(“%d”,&n);
    if(n<0)
       printf(“error:n must>0.”);
       else
    printf(“%d的阶乘为%d.n”,n,fact(n));
    system(“pause”);
    return 0;
}   
   
//计算递归的函数        
long fact(int n)
{
    if(n<=0)
        return -1;
    else
        return n*fact(n-1);
}   

2.计算Fabonacci数列。

基本定义:

f(n)=0,n=0;

f(n)=1,n=1;

f(n)=1,n=2;

f(n)=f(n-1)+f(n-2),(n>2);递归定义。

递归实现:

#include <stdio.h>

//计算数列第n项  
long fib(int n)
{
if (n == 1 || n == 2)  
           return 1;
  return fib(n – 1) + fib(n – 2);
}  

int main()
{  
   int n;
  scanf(“%d”, &n);
  printf(“%ldn”, fib(n));
  return 0;  
}    

一个程序,或者一个算法写好之后,我们自然而然地想到:好有没有更好的实现??这个算法好么??能改进么??

对于这两个程序,效率确实很低下,必须使用更优秀的方式来实现。

一.先分析Fibonacci数列的计算。  
1.感性的认知。  
 
 
  可以看到,f(1)和f(2)被重复计算了很多次,因此效率显得很低下。

  

2.理性分析。     

这里的工作即将集中在程序运行时间的分析上面。

假设,计算第n项需要的时间为T(n)。

由递归关系式知道:T(n) = T(n – 1) + T(n – 2),n >= 3;T(n) = 1。这里的1代表1个CPU单位时间,即CPU计算一个基本语句所需要的时间。 例如,赋值语句,比较大小等等。

先定义一个函数,叫做生成函数,也叫母函数。


 

三.最后,我们来分析计算n的阶乘算法。

 

 


(1)Stirling公式的证明过程如下(来自维基百科):

 

这个公式,以及误差的估计,可以推导如下。我们不直接估计n!,而是考虑它的自然对数

这个方程的右面是积分的近似值(利用梯形法则),而它的误差由欧拉-麦克劳林公式给出:

其中Bk伯努利数Rm,n是欧拉-麦克劳林公式中的余项。取极限,可得:

我们把这个极限记为y。由于欧拉-麦克劳林公式中的余项Rm,n满足:

其中我们用到了大O符号,与以上的方程结合,便得出对数形式的近似公式:

两边取指数,并选择任何正整数m,我们便得到了一个含有未知数ey的公式。当m=1时,公式为:

n趋于无穷大时,两边取极限,并利用沃利斯乘积,便可以得出ey()。因此,我们便得出斯特灵公式:

这个公式也可以反复使用分部积分法来得出,首项可以通过最速下降法得到。把以下的和

用积分近似代替,可以得出不含的因子的斯特灵公式(这个因子通常在实际应用中无关):

[编辑]收敛速率和误差估计

y轴表示截断的斯特灵级数的相对误差,x轴表示所使用的项数。

更加精确的近似公式为:

其中:

斯特灵公式实际上是以下级数(现在称为斯特灵级数)的第一个近似值:

当时,截断级数的误差等于第一个省略掉的项。这是渐近展开式的一个例子。它不是一个收敛级数;对于任何特殊值n,级数的准确性只在取有限个项时达到最大,如果再取更多的项,则准确性将变得越来越差。

阶乘的对数的渐近展开式也称为斯特灵级数:

在这种情况下,级数的误差总是与第一个省略掉的项同号,且最多同大小。

(3)数据分析

至此,数学分析已经臻于完美。

以下是数据:

 

 

 

终于知道,自己为什么学数学了,呵呵 。 微笑  偷笑 大笑   

 

两个算法的迭代版本:
1.斐波那契数列的第n项 

int Fibo(int n){
 
 int a1=1,a2=1; //前两项
 int an ; //第n项 

 if(n==1||n==2)  //n <= 2返回1 
  return 1 ;

 for(int i=3;i<n;i++)
 {
  an=a1+a2;
  a1=a2;
  a2=an;
 }

    return an;
}   

 

2.计算n的阶乘

#include <stdio.h>
int main()
{
 int i,n,s=1;

  scanf(“%d”,&n);
 
  for(i=1;i<=n;i++)
     s*=i;
 
  printf(“%d!=%dn”,n,s);
 
 return 0;
}

    

 
这两个版本都用了一个for循环来实现迭代,只有n次循环就可以完成,效率有了
很大的改善。运行时间都是O(n)。  
 
通过两个例子的分析,递归在某些场合下的效率是很低下的,因此必须使用迭代来实现。
但是,递归并不是不好,关于递归和迭代的转化问题,以下的观点来自这篇博客:
 
 

****不需要消解的递归
那种盲目的消解递归,不惜一切代价躲避递归,认为“递归的速度慢,为了提高速度,必须用栈或者其他的方法来消解”的说法是很片面的。如果一个递归过程用非递归的方法实现后,速度提高了,那只是因为递归做了一些无用功。假使一个递归过程必须要用栈才能消解,那么完全模拟后的结果根本就不会对速度有任何提升,只会减慢;如果你改完后速度提升了,那只证明你的递归函数写的有问题,如多了许多重复操作——打开关闭文件、连接断开数据库,而这些完全可以放到递归外面。可以在本质上是非递归的机器上实现递归过程这一事实本身就证明:为着实际目的,每一个递归程序都可以翻译成纯粹迭代的形式,但这包含着对递归栈的显式处理,而这些运算常常模糊了程序的本质,以致使它非常难以理解。
因此,是递归的而不是迭代的算法应当表述成递归过程。如汉诺塔问题等。汉诺塔问题的递归算法中有两处递归调用,并且其中一处递归调用语句后还有其他语句,因此该递归算法不是尾递归或单向递归。要把这样的递归算法转化为非递归算法,并没有提高程序运行的速度,反而会使程序变得复杂难懂,这是不可取的。也就是说,很多递归算法并不容易改写成迭代程序:它们本质上是递归的,没有简单的迭代形式。这样的递归算法不宜转化为非递归算法。

 

说到底,在我们选择算法时应该全面分析算法的可行性、效率、代码优化。在综合了算法的各个因素后,选择合适的算法来编写程序,这样的程序才会达到优化的效果。

 

四.结束语

数学,是一门艺术,更是一门哲学。

知识共享许可协议
本作品《一个算法设计技巧:递归转化成迭代》verynix创作,采用知识共享署名-非商业性使用-禁止演绎 3.0 Unported许可协议进行许可。
基于verynix.com上的作品创作。
Permissions beyond the scope of this license may be available at verynix.com.

本文链接: http://verynix.com/1015.html

Post Footer automatically generated by wp-posturl plugin for wordpress.

Leave a Reply

Your email address will not be published. Required fields are marked *