---

基本概念#

1. 基本情形：必须总要有某些基准的情形，他们不用递归就能求解。

2. 不断推进：对于那些要递归求解的情形，递归的调用必须总能朝着一个基本情形不断推进。

3. 设计法则：假设所有的递归都能运行。

4. 合成效益法则：在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性工作。比如用递归来计算斐波拉契数列是一种不好的方式。

---

递归实现斐波拉契数列的问题#

在数学上，斐波纳契数列以如下被以递归的方法定义：
F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
代码实现：

public static long fib(int n)
{
  if(n<=1) //第1行
    return 1; //第2行
  else
    return fib(n-1)+fib(n-2); //第3行
}

初看起来，该程序似乎对递归的使用非常聪明并且代码也十分简洁。可是，如果将程序编码并在N为40左右时运行，那么这个程序的效率就非常低了。
下面是测试代码

    public static void main(String[] args) {
        long startTime1 = System.currentTimeMillis();
        System.out.println("f(5)=" + fib(5));
        long endTime1 = System.currentTimeMillis();
        System.out.println("time: " + (endTime1 - startTime1) + "ms");

        long startTime2 = System.currentTimeMillis();
        System.out.println("f(10)=" + fib(10));
        long endTime2 = System.currentTimeMillis();
        System.out.println("time: " + (endTime2 - startTime2) + "ms");

        long startTime3 = System.currentTimeMillis();
        System.out.println("f(20)=" + fib(20));
        long endTime3 = System.currentTimeMillis();
        System.out.println("time: " + (endTime3 - startTime3) + "ms");

        long startTime4 = System.currentTimeMillis();
        System.out.println("f(30)=" + fib(30));
        long endTime4 = System.currentTimeMillis();
        System.out.println("time: " + (endTime4 - startTime4) + "ms");

        long startTime5 = System.currentTimeMillis();
        System.out.println("f(40)=" + fib(40));
        long endTime5 = System.currentTimeMillis();
        System.out.println("time: " + (endTime5 - startTime5) + "ms");

        long startTime6 = System.currentTimeMillis();
        System.out.println("f(50)=" + fib(50));
        long endTime6 = System.currentTimeMillis();
        System.out.println("time: " + (endTime6 - startTime6) + "ms");
    }

结果：

运行时间

从图中可以看出，当N为30时，运行时间为4ms，但是当N为40时，时间为472ms，时间是N为30的100倍，更让人惊讶的是N为50时，时间为58002ms，效率低得令人发指。

当N<=1是，是基本情形，由第1行的判断和第2行的基本赋值运算组成，时间复杂度为T(1)=T(0)=2(第1行的判断和第2行的返回）。当N>2时，执行第1行的判断和第3行的返回语句。第3行由两个方法调用和一个加法组成，由于方法不是简单调用（加减乘除、赋值等），所以它们必须用自己来分析自己。第一次方法调用fib(n-1)，需要T(n-1)个时间单元，第二次方法调用fib(n-2)，需要T(n-2)个时间单元，所以总共需要T(n)=T(n-1)+T(n-2)+2个时间单元（公式中的2为第1 行的判断和第三行的加法）。

这个程序之所以运行缓慢，是因为其存在大量的重复性工作需要做，违反了第4 条规则“合成效益”法则。比如当程序执行第3行第一个函数调用fib(n-1)的时候，递归执行了fib(n-2)，但是当执行第3行第二个函数调用时，又执行了fib(n-2)。容易看出，越是距离基本情形越近的调用，被执行的次数越多，随着N的增加，程序的执行时间成指数增长。