请教一下这个递归函数为什么运行得这么慢，是不是死循环了？
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的时候运行就很慢，不知是什么问题。。 几何级增长的运算量。。。你可以计算器算一下，40!的运算量有多大。。。 他算的不是阶乘
你每递归一次，就相当于调用一次函数，这涉及到入栈和出栈操作，你可以算一下你的函数嵌套的层数 嗯，我弄错了，我当压栈次数成阶乘增长了。
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自己算吧 谢谢指点了，这是C语言二级考试的一条上机题。 我把这个递归函数用两种方法各写了一遍：
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%那么多次，可见冗余的计算量是相当可观的。 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;
} 这不是斐波那契数列吗，直接上通项公式呀！ 斐波那契数列还要再加1，也不完全是斐波那契数列啊，算到40项随便写两行代码就出来了。。 回复【8楼】wwuchang
斐波那契数列还要再加1，也不完全是斐波那契数列啊，算到40项随便写两行代码就出来了。。
-----------------------------------------------------------------------
变种，变种，从第1项（func(1))往后看就是斐波那契数列了，第0项直接赋值0就OK了。
【6楼】 dzqqqq
原题要计算的N=1000，如果按原来的递归算法计算不知要计到猴年马月了~~
所以迭代是很麻烦的，还是通项公式快～～～
页:
[1]