使用尾递归计算Fibonacci数列

核心提示：在过程式,面向对象编程中我们使用递归解决问题的机会不多.但是使用递归方式解决问题是一种比较直观而且简洁的方式,不过编译器对递归没有特别的优化.所以我们很容易写出效率不高的递归程序.而所谓尾递归就是在递归的时候进行计算.下面我以Fibonacci数列为例来说明普通递归和尾递归的不同.普通递归:public long Fi

在过程式,面向对象编程中我们使用递归解决问题的机会不多.但是使用递归方式解决问题是一种比较直观而且简洁的方式,不过编译器对递归没有特别的优化.所以我们很容易写出效率不高的递归程序.而所谓尾递归就是在递归的时候进行计算.下面我以Fibonacci数列为例来说明普通递归和尾递归的不同.　

普通递归:

public long Fib_Common(int n)
　　　　{
　　　　　　if (n == 1 || n == 2)
　　　　　　　　return 1;
　　　　　　else
　　　　　　　　return Fib_Common(n - 1) + Fib_Common(n - 2);
　　　　}

这个实现简单明了就是执行速度太慢了，因为编译器是以如下方式进行计算的（例如计算Fib（6））：

Fib(6) = Fib(5) + Fib(4);
　　　　 = Fib(4) + Fib(3) + Fib(3) + Fib(2);
　　　　 = Fib(3) + Fib(2) + Fib(2) + Fib(1) + Fib(2) + Fib(1) + Fib(2);
　　　　 = Fib(2) + Fib(1) + Fib(2) + Fib(2) + Fib(1) + Fib(2) + Fib(1) + Fib(2);
　　　　 = 8

从上面的递归展开式可以看出Fib(4),Fib(3)都被计算了2次，而且递归函数以2的指数增长。所以当计算到30时就变得非常慢。

尾递归:

public long Fib_Tail(int n)
　　　　{
　　　　　　if (n == 1 || n == 2)
　　　　　　　　return 1;
　　　　　　else
　　　　　　　　return Tail(n, 1, 1, 3);
　　　　}
private long Tail(int n, long b1, long b2, int begin)
　　　　{
　　　　　　if (n == begin)
　　　　　　{
　　　　　　　　return b1 + b2;
　　　　　　}
　　　　　　else
　　　　　　　　return Tail(n, b2, b1 + b2, begin + 1);
　　　　}

再来看看Fib_Tail(3）的计算过程

Fib_tail(6) = Tail(6, 1, 2, 3)
　　　　　　　　　　　　 = Tail(6, 2, 3, 4)
　　　　　　　　　　　　 = Tail(6, 3, 5, 5)
　　　　　　　　　　　　 = 8

这样计算过程都是在每次进入递归函数时计算的（尾部），所以是一个线性增长。只要编译器允许我们可以计算Fib_tail（100）都非常迅速.

正常循环:

public long Fib_Loop(int n)
　　　　{
　　　　　　long b1 = 1, b2 = 1, temp, begin = 3;
　　　　　　for (; begin <= n; ++begin)
　　　　　　{
　　　　　　　　temp = b1;
　　　　　　　　b1 = b2;
　　　　　　　　b2 = temp + b2;
　　　　　　}
　　　　　　return b2;
　　　　}

尾递归一般都是在函数式编程中出现,而且FP语言的编译器有优化,实际上还是尽量转化成循环形式.不过用递归的方式挺锻炼思维的.