斐波那契数列Fibonacci实现（递归、尾递归、循环）

主要内容摘自http://www.cnblogs.com/Anker/archive/2013/03/04/2943498.html

一、递归

简单的来说递归就是一个函数直接或间接地调用自身，是为直接或间接递归。

递归一般用于解决三类问题：

　 (1)数据的定义是按递归定义的。（Fibonacci函数，n的阶乘）
　 (2)问题解法按递归实现。（回溯）
　 (3)数据的结构形式是按递归定义的。（二叉树的遍历，图的搜索）

用线性递归实现Fibonacci函数，程序如下所示：

1 int FibonacciRecursive(int n)
2 {
3     if( n < 2)
4         return n;
5     return (FibonacciRecursive(n-1)+FibonacciRecursive(n-2));
6 }

递归的缺点：

　　递归解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。

在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，因此递归次数过多容易造成栈溢出。

二、尾递归

尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。精髓：尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题，因为参数里带有前面若干步的运算路径。

尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。

采用尾递归实现Fibonacci函数，程序如下所示：

1 int FibonacciTailRecursive(int n,int ret1,int ret2)
2 {
3    if(n==0)
4       return ret1; 
5     return FibonacciTailRecursive(n-1,ret2,ret1+ret2);
6 }

尾递归实现Fibonacci函数（C++实现）

#include <iostream>
#include <time.h>
using namespace std;
/**
 斐波那契数列Fibonacci
 一对小兔子两月具有繁殖能力，每月生一对
 经过月数：0 1 2 3 4 5 6 7 ...
 兔子对数：0 1 1 2 3 5 8 13 ...
*/

//传统递归实现normal recursion
unsigned long fib_normal_rec(unsigned long n)
{
if (n <= 2)
return 1;
else
return fib_normal_rec(n-1) + fib_normal_rec(n-2);
}

//尾递归实现Rail recusion
unsigned long fib_rail_rec(unsigned long n, unsigned long first, unsigned long second)
{
if (n == 1) return first;
if (n == 2) return second;
return fib_rail_rec(n-1, second, second+first);
}
unsigned long fib_rail_rec(unsigned long n)
{
return fib_rail_rec(n, 1, 1);
}

//循环实现
unsigned long fib_no_rec(unsigned long n)
{
if (n <= 2)
return 1;
unsigned int x=1, y=1, y_tmp=0;
//else if(n>=3)
for (unsigned int i=0; i<n-2; i++)
    {
        y_tmp = y;
        y = x+y;
        x = y_tmp;
    }
return y;
}

double calcRunTime(clock_t start, clock_t finish)
{
return (double)(finish-start)/CLOCKS_PER_SEC;
}

int main()
{
//第50个斐波那契数已经快接近(2^32)-1了，而且(win7 64位 i7-3.4GHz*8核)跑了54秒
//再大时间太长没等了，普通递归实现斐波那契数运行时间基本为指数增长，且因递归调用耗CPU，栈开销耗内存
//第几个--斐波那契数是几：24--46368; 25--75025
unsigned long order_num = 50; //表示第order_num个斐波那契数
unsigned long fib_num = 0;    //表示第order_num个斐波那契数是fib_num

    clock_t start0, finish0, start1, finish1, start2, finish2;

    start0 = clock();
    fib_num = fib_normal_rec(order_num);
    finish0 = clock();
cout << "第" << order_num << "个斐波那契数是：" << fib_num <<endl;
cout << "普通递归实现斐波那契数耗时（秒）:" << calcRunTime(start0, finish0) << endl;
cout << "----------------------------------------------------------" << endl;

    start1 = clock();
    fib_num = fib_rail_rec(order_num);
    finish1 = clock();
cout << "第" << order_num << "个斐波那契数是：" << fib_num <<endl;
cout << "尾递归实现斐波那契数耗时（秒）:" << calcRunTime(start1, finish1) << endl;
cout << "---------------------------------------------------------" << endl;

    start2 = clock();
    fib_num = fib_no_rec(order_num);
    finish2 = clock();
cout << "第" << order_num << "个斐波那契数是：" << fib_num <<endl;
cout << "普通循环实现斐波那契数耗时（秒）:" << calcRunTime(start2, finish2) << endl;
cout << "----------------------------------------------------------" << endl;

    system("pause");
return 0;
}