递归式斐波那契与循环式斐波那契之间有明显的计算时间差吗？我使用递归将Fibonacci一直运行到40个地方，然后再直接使用循环。看来计算时间差只是academic。
用C语言编写
递归解决方案：
int main(int argc, const char * argv[]) {
int n, i = 0, c;
printf("Please enter an integer:\n");
scanf("%d", &n);
for ( c = 1 ; c <= n ; c++ )
{
printf("%lu ", fibonacci(i));
i++;
}
return 0;
}
long fibonacci(long n)
{
if ( n == 0 )
return 0;
else if ( n == 1 )
return 1;
else
return ( fibonacci(n-1) + fibonacci(n-2) );
};
循环解决方案：
int main(int argc, const char * argv[]) {
int n, first = 0, second = 1, next, c;
printf("Please enter an integer:\n");
scanf("%d", &n);
for ( c = 0 ; c < n ; c++ )
{
if ( c <= 1 )
next = c;
else
{
next = first + second;
first = second;
second = next;
}
printf("%d ",next);
}
return 0;
};
与尾部递归和迭代版本相比，常规递归方法非常慢。在下面的迭代版本示例代码中，使用展开的循环以及Duff's Device进入循环。对于32位无符号整数，限制为fib（47），对于64位无符号整数，限制为fib（93）。
使用Intel 2600K 3.4ghz，XP X64、64位模式进行计时。 XP或XP X64高性能计数器频率与CPU时钟相同，为3.4GHz，但是如果持续时间较小，则操作系统开销（如中断）会影响时序。
fib（40）的时间：
fibr() # of microseconds 485468.8
fibt() # of microseconds 0.2
fibi() # of microseconds 0.2
为94个循环计时，n = 0至93：
fibt() # of microseconds 7
fibi() # of microseconds 5
示例代码：
typedef unsigned long long UI64;
UI64 fibr(UI64 n)
{
if(n < 2)
return n;
return fibr(n-1) + fibr(n-2);
}
// call with fibt(n, 0, 1)
UI64 fibt(UI64 n, UI64 res, UI64 next)
{
if (n == 0)
return res;
return fibt(n - 1, next, res + next);
}
UI64 fibi(UI64 n)
{
UI64 f0, f1, i;
if(n < 2)
return n;
n -= 2;
f1 = f0 = 1;
i = 0;
switch(n%8){
do{
f1 += f0;
case 7:
f0 += f1;
case 6:
f1 += f0;
case 5:
f0 += f1;
case 4:
f1 += f0;
case 3:
f0 += f1;
case 2:
f1 += f0;
case 1:
f0 += f1;
case 0:
continue;
}while(n >= (i += 8));
}
return f0;
}
fibi（）的替代版本，不进行n <2的检查。 f0和f1代表循环内的变化，最终以f0的最终和结束，因此f0和f1代表的初始状态取决于n是偶数还是奇数。如果n为偶数，则f0 = fib（0）= 0，f1 = fib（-1）= 1，如果n为奇数，则f1 = fib（0）= 0，f0 = fib（-1）= 1。 （如果您好奇，fib（-1）= 1，fib（-2）= -1，fib（-3）= 2，fib（-4）= -3，fib（-5）= 5， fib（-6）= -8，...）。
要在这里解释逻辑，对于n个偶数情况，fib（-1）= f1 = 1，fib（0）= f0 = 0，然后fib（1）=（f1 + = f0），fib（2） =（f0 + = f1），fib（3）=（f1 + = f0），fib（4）=（f0 + = f1），...。
UI64 fibi(UI64 n)
{
UI64 f0, f1, i;
f0 = n & 1; // if n even, f0=0, f1=1
f1 = 1 - f0; // else f1=0, f0=1
i = 0;
switch(n%8){
do{
f1 += f0;
case 7:
f0 += f1;
case 6:
f1 += f0;
case 5:
f0 += f1;
case 4:
f1 += f0;
case 3:
f0 += f1;
case 2:
f1 += f0;
case 1:
f0 += f1;
case 0:
continue;
}while(n >= (i += 8));
}
return f0;
}
for循环不一定更快。在像Java，C和Python这样的通用语言中，与迭代相比，递归是相当昂贵的，因为它需要分配新的堆栈框架。
可以消除C / C ++中的这种开销，从而使编译器优化能够执行尾部递归，该尾部递归将某些类型的递归（实际上是某些类型的尾部调用）转换为跳转而不是函数调用。为了让编译器执行此优化，必须在调用函数之前做的最后一件事是调用另一个函数（在本例中为自身）。
斐波那契函数的示例可能是这样的：
int fib_tail(int n, int res, int next)
{
if (n == 0) {
return res;
}
return fib_tail(n - 1, next, res + next);
}
并且在汇编级别，启用编译器优化，它将作为循环实现，例如在调用之间共享相同的堆栈框架。
我最近为此写了article。
希望有帮助。
For-loop解决方案更快。原因：
n次使用n加法（循环迭代n次），而递归解决方案对每个函数调用使用一个加法，该加法等于O(1.6n)次调用，因此O(1.6 [C0 ] n添加。代价来自两次递归调用-当递归函数要求第)个元素时，它不得不从头开始再次计算第O(1.6个元素和第n个元素，它不记得了。您如何测量速度差？
也许下面的方法会花费更少的时间？您可以编写代码来生成斐波那契数列，从而避免if-else语句显示零和一，并避免在循环外打印它们。您可以通过用-1和1初始化'first'和'second'变量来做到这一点，因此它们之间的总和将为0，这是该系列的第一个器官，而循环将完成其余的工作。