Fibonacci数列的非递归实现

用递归方法计算阶乘的代码如下：

//递归计算阶乘
long Factorial(int n)
{
if (n <= 0)
{
return 1;
}

return n * Factorial(n - 1);
}

这样的递归是一个很明显的尾部递归的例子，所谓的尾部递归（tail recursion），即递归调用是函数执行的最后一项任务，函数在递归调用返回之后不再做任何事情。尾部递归可以很方便的转换成一个简单循环，完成相同的任务，这样，就将一个递归的实现转化成了非递归实现。

以下是阶乘算法的非递归实现：

//计算阶乘的非递归实现
long Factorial(int n)
{
long result = 1;

while (n > 1)
{
result *= n;
n--;
}
return result;
}

单从这个改写来看，我们无法看出这样的改写有多大的意义。但是有些时候，递归并不是一种很好的解决问题的方法，最常见的一个问题就是深度递归会造成堆栈溢出的错误！有时候递归还会导致程序效率的下降，下面要说的Fibonacci数列，就是一个很好的反例。

Fibonacci数列使用递归的定义（呃。。。定义就不给了），这种定义容易诱导我们使用递归形式来编程解决这个问题。下面是一个Fibonacci的递归实现，很容易就看懂了，呵呵，就是定义的程序版本：

//递归计算Fibonacci数列的值
typedef unsigned long ulong;
ulong Fiblnacci(int n)
{
if (n <= 2)
{
return 1;
}
return Fiblnacci(n - 1) + Fiblnacci(n-2);
}

这样的程序是非常简捷的，有时候，递归的程序实现看上去要比非递归的实现简捷得多。这个时候，你需要在效率和程序的可读性和可维护性上做一些取舍。

这个Fibonacci的递归实现在计算值时，每次递归调用都触发另外两个递归，而这两个递归在调用的时候每个都还要触发两外的两个递归调用，再接下去的调用也是如此。现在，我们知道，这个冗余的递归调用是以几何级数增长的。例如，在递归计算Fibonacci(10)时，Fibonacci(3)的值被计算了21次。而在递归计算Fibonacci(30)，这个调用的次数是骇人的317811次！这些个计算实际上只有一次是必要的，其余的纯属浪费！

下面的程序使用一个简单循环来代替递归，这个非递归的形式不如上文给出的递归简单（当然，这个也很简单），也不太符合Fibonacci的递归定义，但是，它的效率提高了几十万倍！

//Fibonacci数列的非递归实现
typedef unsigned long ulong;

ulong Fibonacci(int n)
{
ulong result;
ulong prev_result;
ulong next_result;

result = prev_result = 1;

while (n > 2)
{
n--;
next_result = prev_result;
prev_result = result;

result = prev_result + next_result;
}

return result;
}

所以，本文的结论就是，当你使用递归实现一个函数之前，先问问自己使用递归的好处是否抵得上它的代价。当然，编程的时候，无论什么实现方式，我们都应该问问自己这个问题。