递归函数比它们的非递归函数慢吗？
递归函数比它们的非递归函数慢吗？
提问于 2017-03-25 11:15:00
我对一个数的阶乘和Fibonacci级数使用了一个递归函数(在C++中完成)，并且我发现关于阶乘的递归函数按照预期正常运行，并且执行速度没有太大的差别。
然而，在斐波纳契号上，它显然是缓慢的。为什么会这样呢？
递归方法：
unsigned long int fib_num(int n) //This is My code
{
switch (n)
{
case 1:
return 0;
break;
case 2:
return 1;
break;
default:
return fib_num(n - 1) + fib_num(n - 2);
break;
}
}迭代方法：
first = 0;
second = 1
for(i = 0; i < num; i++)
{
cout<<"\n"<<first;
next = first + second;
first = second;
second = next;
}Stack Overflow用户
发布于 2020-05-08 21:50:50
我将给出一个Fibionacci系列的例子。
recursive 41 index calculated pass time 1.343 seconds
non recursive 40000 index calculated pass time 1.042 seconds这是我们的密码。
public static void main(final String[] args) {
long before = new Date().getTime();
for(int i = 0; i <= 41; i++) {
findRecursiveFibionacci(i);
}
System.out.println("recursive 41 index calculated pass time "+((float)(new Date().getTime()-before)/1000) + " seconds");
long before2=new Date().getTime();
for(int i = 0; i <= 40000; i++) {
getFib(i);
}
System.out.println("non recursive40000 index calculated pass time "+((float)(new Date().getTime()-before2)/1000) + " seconds");
}
public static long getFib(final int index) {
long a=0,b=0,total=0;
for(int i=0;i<= index;i++) {
if(i==0) {
total=a+b;
a=0;
}else if(i==1) {
b=1;
total=a+b;
}else if(i%2==0) {
total=a+b;
a=total;
}else {
total=a+b;
b=total;
}
}
return total;
}
public static long findRecursiveFibionacci(final int a ){
if(a==0)return 0;
if(a<=2)return 1;
final long fibterm = findRecursiveFibionacci(a-1)+findRecursiveFibionacci(a-2);
return fibterm;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43015659
复制相关文章
相似问题
腾讯云开发者
