回 帖 发 新 帖 刷新版面

主题:[原创]小试递归算法与循环算法在Fibonacci数列求解中的运算效率

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

小试递归算法与循环算法在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

回复列表 (共20个回复)

沙发

[em14]这还初级呢,我都没有看懂,呵呵[em5]

板凳

什么是Fibonacci数列??

我想知道你测试的结论?我猜是循环快,是吗?

3 楼

是的~
Fibonacci数列的规则是:

第1、2个元素是1,从第3个元素开始,每个元素是前两个元素之和。
这个很简单的,今天照书上写例题,忽然想看看递归的运算速度,于是写了个程序测试,结果大吃一惊,想不到运算时如此惊人,于是又想到了用其它方法写一下做对比。
我的结论是,用递归运算量过大,但没试过用递归求解其它问题时的运算效率,不敢下妄语,只是就事论事,说一下用它解Fibonacci数列缺点。
我把那个测试程序代码也在这里发一下,写得很乱,仅供大家参考。

#include <iostream.h>

long fib(int n);
long fib1(int n);
long fib2(int n);
long fib3(int n);
int i,m;
void main()
{
    i=0;
    m=0;
    int n;
    long result=0;

    cout<<"Input n: ";
    cin>>n;

    cout<<endl;
    cout<<"n="<<n<<endl;
    result=fib3(n);

    cout<<"======================="<<endl<<"  Result = "<<result<<endl;
    cout<<"  Times="<<i<<endl;    
}

long fib3(int n)
{    
    long c1=0,c2=0,c=0;
    i++,m++;                 
    cout<<endl<<"Times:"<<i<<endl<<"  n="<<n<<endl;
    cout<<"  level="<<m<<endl;
    switch(n)
    {
        case 0:{m-=2;cout<<"  n=0"<<",return c=0"<<endl;return 0;}
        case 1:{m-=2;cout<<"  n=1"<<",return c=1"<<endl;return 1;}
        case 2:{m-=2;cout<<"  n=2"<<",return c=1"<<endl;return 1;}
    }
    cout<<"  call c1=fib(n-1)=fib("<<n<<"-1),next n maybe "<<n-1<<endl;
    c1=fib(n-1);
    cout<<"    return c1=fib(n-1)=fib("<<n<<"-1)="<<c1<<endl;

    cout<<"  call c2=fib(n-2)=fib("<<n<<"-2),next n maybe "<<n-2<<endl;
    c2=fib(n-2);
    cout<<"    return c2=fib(n-2)=fib("<<n<<"-2)="<<c2<<endl;
    c=c1+c2;
    cout<<"  c=fib(n)=fib(n-1)+fib(n-2)=fib("<<n<<")="<<c<<endl;
    cout<<"  return c="<<c<<endl;
    return c;
    
}

4 楼

不好意思,一时大意忘把fib()、fib1()、fib2()的声明去掉了

5 楼

我觉得递归慢的原因是,每调用一次递归函数,就会重新把整个函数的信息全部读入系统,而且是临时的,在程序运行前调用的次数是未知的,所以速度不快。而循环重馥 的只是数据变量,没有把整个函数重得调用。
其实不用递归也可以实现递归,用数据保存

6 楼

用递归算fibonacci慢的原因是重复计算。
例如计算fib(5)时用到了fib(3)和fib(4),计算fib(4)时又用到了fib(3)和fib(2),其中fib(3)被计算了两次,造成极大浪费。
如果在递归中保存已经算过的值到一个全局的数组中,用到的时候如果算过就直接取来用,则递归的效率跟循环相差无几。

7 楼

楼上高手

8 楼

感谢大家的回复。学习的最有效途径是多多交流,希望大家能多多把自己的观点看法写成贴发表在论坛里,通过听取大家的意见一定会有更多的收获。

9 楼

6楼果然高手,我也曾看过某本书对于递归的描述,难得6楼能记得这么清楚,而我却不能,惭愧~~~
其实我也很少想到会去用递归,一则效率差,二则对于大的输入有可能造成程序不能运行,因为它对于主
存资源很是挥霍,不过它有一个优点就是“整洁干净利落”。
[em5]

10 楼

楼主说得是!

我来回复

您尚未登录,请登录后再回复。点此登录或注册