递归程序是把双刃剑


在我原来的概念里,递归程序是简洁、巧妙、高效的代名词,但是读了《Data Structure And Algorithm Analysis in C》之后,我才发现原来自己之前的认识是错误的,至少递归程序不总是高效的代名词,如果使用不当,将会有很大的性能(效率)问题。

1. 两个例子

(1)使用递归实现阶乘:

long int Factorial(int N)
{
    if ( N <= 1 )
        return 1;
    else
        return N * Factorial(N-1);
}

(2)使用递归求斐波那契数列:

long int Fibonacci(int N)
{
    if ( N <= 1 )
        return 1;
    else
        return Fibonacci( N - 1 ) + Fibonacci( N - 2 );
}

分析:

这两个例子都是使用递归实现,代码也很相似,但是效果却是恰恰相反的。我们分别进行分析:

对于第一个例子,虽然使用了递归,但其实很容易就可以改成一个for循环,循环次数为N,所以第一个函数的复杂度(本文的复杂度都指时间复杂度)和N次for循环是一样的,为O(N)。证明如下:

设Factorial(N)的运行时间为P(N),则由递归可知一次Factorial(N)耗时为第3行的if判断(耗时为1)加上第6行的一次乘法(耗时为1),以及一次函数调用(耗时为P(N-1)),所以有:P(N)=1+1+P(N-1)=P(N-1)+2,注:计算复杂度是我们一般不关注常数,常数系数也不关注。很明显,这是一个等差数列,且P(1)=1,公差为2,所以P(N)=P(1)+(n-1)*2=O(n)。

而第二个例子,却是非常糟糕的。和上例相同,我们来计算一下Fibonacci(N)的复杂度:

设Fibonacci(N)运行时间为T(N),则T(N)=T(N-1)+T(N-2)+2,“2”指的是if判断和后面的一次加法。而Fibonacci(N)=Fibonacci(N-1)+Fibonacci(N-2),因此由归纳法可以证明T(N)≥Fibonacci(N)。而当N>4时,有Fibonacci(N)≥(3/2)N(后面证明)。所以,可以看出这个函数的运行时间以指数的速度增长。但是如果我们使用数组来实现该函数,则其复杂度为O(N)。

为什么第二个递归程序的效率这么差呢?因为它做了很多多余的工作。比如在计算Fibonacci(N-1)的时候实际上已经计算了Fibonacci(N-2),而后面又再计算了一次Fibonacci(N-2).这样递归下来,做这些多余工作所耗费的时间便变得非常的大。这在递归程序中是非常忌讳的。

2. 编写递归程序的四个基本法则

编写递归程序时只要遵守一些规则,便可以很好的使用递归有利的一面。下面列出四个基本法则:

  • 基准情形(base case)——必须总有某些基准情形,它无须递归就能解出。比如上面的两个例子,当N ≤ 1时,无须递归便可计算出结果,这便是它们的基准情形。如果没有这个基准情形,则递归是毫无意义的。
  • 不断推进(making progress)——对于那些需要递归求解的情形,每一次递归调用都必须要使求解状况朝接近基准情形的方向推进。
  • 设计法则(design rule)——假设所有的递归调用都能运行。
  • 合成效益法则(compound interest rule)——在求解一个问题的同一实例时,切勿在不同的递归调用中做重复性的工作。上面第二个例子便是一个很好的证明。

3. 递归与循环逻辑

很多时候,递归都可以被循环替代,但迭代使用的并不是循环逻辑(circular logic):

  • 递归逻辑——用一个函数本身去定义这个函数
  • 循环逻辑——用函数本身去定义该函数一个特定的实例

举例来说,使用Factorial(N)来得到Factorial(N)的值是循环逻辑,但通过Factorial(N-1)来的得到Factorial(N)的值不是循环逻辑,除非Factorial(N-1)又依赖于Factorial(N)。

:循环和循环逻辑不是一个概念,一个循环可能使用的也是迭代逻辑。

4. 函数调用

这里要介绍函数调用是因为递归调用其实也是一种函数调用,没有什么特殊之处。当调用一个新的函数时,主调例程的所有局部变量需要由系统存储起来,否则被调用的新函数将会覆盖调用例程的变量。不仅如此,该主调例程的当前位置也要存储,以便新函数运行完以后知道向哪里转移。这些变量一般由编译器指派给机器的寄存器,但存在某些冲突(通常所有的过程都将某些变量指派给1#寄存器),特别是涉及递归的时候。

当存在函数调用的时候,需要存储所有重要的信息,诸如寄存器的值(对应变量的名字)和返回地址(它可从程序计数器PC得到,典型情况下计数器就是一个寄存器)等,都要以抽象的方式存在“一张纸上”并被置于一个堆(pile)的顶部。然后控制转移到新函数,该函数自由的用它的一些值代替这些寄存器。如果它又进行其他的函数调用,那么它也遵循相同的过程。当该函数返回时,它查看堆(pile)顶部的那张“纸”并复原所有的寄存器。然后它进行返回转移。而所有这些工作均是由栈来完成的。所存储的信息称为活动记录(activation record)或者栈帧(stack frame)。如果同时运行的函数太多或者某个函数使用的栈帧特别多,那将有可能用尽栈空间,从而导致程序崩溃。而且很多系统是不检测栈溢出的。

这里我们看另外一种糟糕的递归:

void PrintList(List L)
{
    if ( L != NULL)
    {
        PrintElement( L->Element );
        PrintList( L->next );
    }
}

这个程序递归的遍历一个链表,程序完全合法且表面上也是无害的,符合前面介绍的四个基本规则。但它却是非常糟糕的一种实现,因为当链表的信息非常多时,在递归调用时我们很可能会将栈空间耗尽。

5. Fibonacci(N)≥(3/2)N(N>4)的证明

这里我们使用归纳法证明该命题,证明之前先回忆一下归纳法的标准步骤:

第一步:证明基准情形(base case),就是确定定理对某个(某些)小的(通常是退化的)值的正确性。这一步一般都是很简单的。

第二步:进行归纳假设(inductive hypothesis),就是假设定理对直到某个有限数k的所有情况都是成立的。然后使用这个假设证明定理对下一个值(通常是k+1)也是成立的。

经过上面两步,便可证明定理是成立的。下面附上证明过程:

formula1

可见,递归是一把双刃剑,我们必须合理使用。最后再次声明一下,递归并不是循环的一种替代品,尽管很多时候二者可以相互转化。


已有 2 条评论

  1. hongliming@foxmail.com

    <img src="http://img.t.sinajs.cn/t35/style/images/common/face/ext/normal/d0/z2_org.gif" />

    hongliming@foxmail.com 回复
    1. 时间轨迹
      @hongliming@foxmail.com

      <img src="http://img.t.sinajs.cn/t35/style/images/common/face/ext/normal/89/hufen_org.gif" />

      时间轨迹 博主 回复

添加新评论

选择表情 captcha

友情提醒:不填或错填验证码会引起页面刷新,导致已填的评论内容丢失。

|