请教一下这个递归函数为什么运行得这么慢，是不是死循环了？

dzqqqq

long fun2(int Num)
{
if(Num==0)return 0;
if(Num==1)return 1;

return (fun2(Num-2)+fun2(Num-1));
}


int main(int argc,char *argv[])
{
  printf("%lu  ",fun2(50));
}

当参数Num 大于40的时候运行就很慢，不知是什么问题。。

snoopyzz

几何级增长的运算量。。。你可以计算器算一下，40!的运算量有多大。。。

liaowei

他算的不是阶乘
你每递归一次，就相当于调用一次函数，这涉及到入栈和出栈操作，你可以算一下你的函数嵌套的层数

snoopyzz

嗯，我弄错了，我当压栈次数成阶乘增长了。
n = 2时，调用次数=1+1+1=3
n = 3时，调用次数=3+1+1=5
n = 4时，调用次数=3+5+1=9
n = 5时，调用次数=5+9+1=15
n = 6时，调用次数=9+15+1=25
n = 7时，调用次数=15+25+1=41
n = 8时，调用次数=25+41+1=67
n = 40 时，fun2的调用次数LZ自己算吧

dzqqqq

谢谢指点了，这是C语言二级考试的一条上机题。

jimo

我把这个递归函数用两种方法各写了一遍：

int func1(int n)
{
    if (n <= 1) return n;
    return func1(n - 1) + func1(n - 2);
}

__int64 func2(__int64 n, __int64 *a1 = NULL)
{
    if (n == 0) return 0;
    else if (n == 1)
    {
        if (a1) *a1 = 0;
        return 1;
    }
    else if (n == 2)
    {
        if (a1) *a1 = 1;
        return 1;
    }
    __int64 p, q;
    __int64 k = func2(n - 1, &p);
    if (a1) *a1 = k;
    return p + k;
}

然后调用：
    DWORD tick1 = GetTickCount();
    int w = func1(40);
    DWORD tick2 = GetTickCount();
    int x = func1(41);
    DWORD tick3 = GetTickCount();
    int y = func1(42);
    DWORD tick4 = GetTickCount();
    __int64 z = func2(50);
    DWORD tick5 = GetTickCount();

结果：
tick2 - tick1 = 11047
tick3 - tick2 = 17834
tick4 - tick3 = 28938
tick5 - tick4 = 0


再调用：
    DWORD tick4 = GetTickCount();
    __int64 z = func2(100);
    DWORD tick5 = GetTickCount();

结果：
tick5 - tick4 = 0

高效递归函数的关键，在于处理递归函数里面的历史计算结果。f(n)被多次调用，如果每次调用的结果都是相同的，那么就要把f(n)的值记录下来，这样就可以迅速的完成计算。
第一种方法之所以慢，是因为计算f(n)，n加1，f(0)就要多调用62%那么多次，可见冗余的计算量是相当可观的。

dzqqqq

LS 厉害，分析得很透彻！

原题要计算的N=1000，如果按原来的递归算法计算不知要计到猴年马月了~~

我分析一下这个函数的规律，使用了另一种算法，这样就很快捷了。

long fun(int Num)
{
  int s,n=2,pre1=1,pre2=1;

  
  if(n==Num)return 1;

  while(1)  //n>=3
  {
   s=pre1+pre2;
   pre2=pre1;
   pre1=s;
   if(++n>=Num)break;
  }

  return s;

}

takashiki

这不是斐波那契数列吗，直接上通项公式呀！

wwuchang

斐波那契数列还要再加1，也不完全是斐波那契数列啊，算到40项随便写两行代码就出来了。。

takashiki

回复【8楼】wwuchang  
斐波那契数列还要再加1，也不完全是斐波那契数列啊，算到40项随便写两行代码就出来了。。
-----------------------------------------------------------------------

变种，变种，从第1项（func(1))往后看就是斐波那契数列了，第0项直接赋值0就OK了。

【6楼】 dzqqqq
原题要计算的N=1000，如果按原来的递归算法计算不知要计到猴年马月了~~
所以迭代是很麻烦的，还是通项公式快～～～