前言：可能太初级了，如果版主感觉层次太低删掉或丢到初学园地里。

小试递归算法与循环算法在Fibonacci数列求解中的运算效率

作者：KKND
时间：2004年9月1日

源程序代码如下：

//  Fibonacci数列第N项求解算法对比程序，VC 6.0 编译通过

#include <iostream.h>

long fib1(int n);
long fib2(int n);

int i=0;  //运算次数计数器


//---------------start main()------------
void main()
{
    int n=0;

    cout<<"Input a int number:";        //显示提示信息
    cin>>n;                    //输入参数 n
    
    cout<<endl<<endl;            //显示两个空行

    //测试使用递归算法的情况------------------

    i=0;  //运算次数计数器清零

    cout<<"fib1("<<n<<")="<<fib1(n)<<endl;//输出结果
    cout<<"  Times="<<i<<" (Call Back Times!) "<<endl;//输出计算次数
    cout<<endl;

    //结果表明运算效率相当差，递归调用的次数居然达到了运算结果数值的2倍-1次。
    //在n=20的情况下调用次数竞达到13529次。
    //不过从中得到的启示是，是否可以利用这个规律得出通用的计算公式。
    //即   计算结果=(递归调用次数+1)/2


    //测试使用循环算法的情况------------------

    i=0;  //运算次数计数器清零

    cout<<"fib2("<<n<<")="<<fib2(n)<<endl;//输出结果
    cout<<"  Times="<<i<<" (Loop Times!) "<<endl;//输出计算次数
    cout<<endl;

    //结果表明运算效率很高，总运算次数连前面的条件判断加起来只有 n 次
    //在n=20的情况下只需要循环18次，连2次判断可认为计算20次。

}//----------------end main()--------------


//---------------start fib2()------------
long fib1(int n)    //利用递归调用
{    
    i++;                    //运算次数计数器，不计入算法复杂性统计。
    switch(n)               //
    {                        //
        case 0:return 0;    //-----每次调用时都无法跳过的判断运算（复杂性不明）。
        case 1:                //
        case 2:return 1;    //
    }                        //
    
    return fib1(n-1)+fib1(n-2);        //主要计算语句，每次调用有两次加法等效运算和一次返回（至少相当于赋值），而且还要进行递归调用（复杂性不明）。
}//--------------end fib1()--------------


//---------------start fib2()------------
long fib2(int n)    //利用循环语句
{    
    int k=0;
    long a=1,b=1,c=0;
    
    if(n==0)            //根据n值不同可算做1至3次判断运算计入算法复杂性。
    {                    //
        return 0;        //
    }                    //
    else if(n==1||n==2)    //--|
    {                    //  |
        return 1;        //  |---若考虑通用性，此初始条件判断可以移入循环体，但效率将不是最优化，
    }                    //--|   移入循环体会在每次循环增加1至2次判断运算，增加了算法复杂性。
    else
    {
        for(k=2;k<n;k++)
        {
                  
            b=a+(c=b);    //
            a=c;        //（或写成c=b;b=a+b;a=c;）实际运算语句，只有一个加法和三个赋值。
        
            i++;        //运算次数计数器，不计入算法复杂性统计。
        }
        return b;
    }
}//--------------end fib2()--------------


/*上面的fib2()代码精简形式如下：

long fib2(int n){
    int k=0;
    long a=1,b=1,c=0;

    if(n==0)
        return 0;
    if(n==1||n==2)
        return 1;
    for(k=2;k<n;k++){
        b=a+(c=b);a=c;
    }
    retrun b；
}
------------------*/

QQ：20587039
E-mail: li-Q_Q@163.com