用递归来计算斐波那契数列很慢是咋回事

用递归来计算斐波那契数列很慢是怎么回事？
源代码如下：

#include <stdio.h>

unsigned long long  func(unsigned int n)
{
if(n == 1 || n== 2)
{
return 1;
}
return func(n - 1) + func(n - 2);
}

void main()
{
unsigned int n;
printf("请输入要得到的是第几个数：");
scanf("%u" , &n);
printf("%llu\n" , func(n));
}

我用的编译器是Visual C++ 2010旗舰版，当输入40的时候就比较慢，如果是41，42，43，44就更慢了，如果输入50，100，150之类比较大的数就几乎不能显示结果了，在很多台电脑上都试过了，都不行，不知道是怎么回事。但是如果用递推的方法来做的话就会很快，即使输入150，200之类很大的数的话也很快，请高人帮忙看下，谢谢！
[解决办法]
递归过程中,系统建立堆栈来保存上一层状态信息, 
和退栈获取还原系统状态都要有开销的.系统做的事情不少, 
所以效率要低. 
不过递归容易写，容易读懂,而且代码一般比较精简.
[解决办法]
递归次数太多会导致栈溢出。
可以缓存已计算过的结果。

[解决办法]
其实这不是递归的错，如果你能换一种算法，同样使用递归，可以更加快速的解决问题
首先，斐波那契数列是这样的0,1,1,2,3,5,8,13,21...
它是满足a(n)=a(n-1)+a(n-2)的第一项和第二项分别为0和1的数列
在数学中满足a(n)=a(n-1)+a(n-2)的序列称之为加法序列,这里我们的想法是利用斐波那契函数调用加法序列函数，通过观察可以得知，加法序列函数返回的是前两项之和，那么我们的想法是让它返回的是函数参数，这样算法就简单多了，以下是代码
int fib(int n)
{
   return addorder(n,0,1);
   
}
 
int addorder(int n,int a0,int a1)
{
   if(n==0) return a0;
   if(n==1) return a1;
   else
   return addorder(n,a1,a0+a1);
}

[解决办法]
我在计算过程中把一些结果存在全局数组中, 果然要少计算很多. 楼主可以试一下:

#include <stdio.h>
unsigned long long fb[100] = {0};//保存结果的全局数组
unsigned long long  func(unsigned int n)//利用全局数组的函数
{

unsigned long long result = 0;
if(n==0 
[解决办法]
 n==1)
{
fb[n] = 1;

result = 1;
printf("x = %d\t%d\n",n,result);//这个地方是我把计算的情况显示出来,
//也可以弄一个全局变量做计数器, 在每个分支里都+1, 这样可以显示出计算的次数. 
}
else
{
if(fb[n-1] == 0)
{

result = func(n-1) + func(n-2);
fb[n] = result;
printf("n = %d\t%d\n",n,result);
}
else
{

result = fb[n] = fb[n-1] + fb[n-2];
printf("y = %d\t%d\n",n,result);
}
}
return result;
}

unsigned long long  func1(unsigned int n)//纯计算的函数
{

unsigned long long result = 0;
if(n==0 
[解决办法]
 n==1)
{
result = 1;
printf("x = %d\n",n);
}
else
{
result = func1(n-1) + func1(n-2);
printf("n = %d\t%d\n",n,result);
}
return result;
}

int main(){
    int n = 42;
unsigned long long result = func(n);
printf("%d\n\n\n\n",result);
//result = func1(n);
//printf("%d",result);

system("pause");
    return 0; 
 
} 

查看更多 下一篇