在我原来的概念里，递归程序是简洁、巧妙、高效的代名词，但是读了《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

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