关于fibonacci序列迭代和递归算法在C语言和scheme语言下实现存在差异的疑惑
最近在学 Mit OCW 上的 SICP课程中，发现了二个分别用递归和迭代实现fibonacci序列的算法，书上用的是scheme语言来实现，后来，我又自己用C语言来实现，具体代码如下：
[color=#FF0000]Dr Scheme:[/color]
;用递归
(define (fib n) (cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))))
(fib 35)
；用迭代
(define (fiba n)(fib-iter 1 0 n))
(define (fib-iter a b count)(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
(fiba 38)
-------------------------------------------------------------------
[color=#FF0000]Visual C++ 6.0：[/color]
#include <stdio.h>
#define Recursion
#ifdef Recursion /* 递归算法 */
int Fibonacci(int n)
{
if(n < 0)
printf( "The fibonacci number exists only with nonnegative index.\n ");
else
{
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
#else /* 迭代算法 */
int Fibonacci_iter(int a, int b, int count)
{
if(count == 0)
return b;
else
return Fibonacci_iter(a + b, a, count - 1);
}
int Fibonacci(int n)
{
return Fibonacci_iter(1, 0, n);
}
#endif
int main()
{
printf( "fib(38): %d.\n ", Fibonacci(38));
}
---------------------------------------------------------------
结果：
在 DrScheme下实现的这两个算法千差万别， 用递归的算法明显比迭代算法慢（在我的机器上，用迭代可以在1s内求得
fib(1000)，而用递归则必须用5s来实现fib(35)，）
在 visual C++ 6.0下实现这两个算法却没有多大的区别(两个算法都是到了fib(35)以后就速度慢如牛）。
----------------------------------------------------------------
疑惑：
难道在Visual C++ 6.0下， 这两个算法都是递归算法，那么递归和迭代的区别究竟是什么？为什么同样的算法在不同的语言实现下有不同的结果？Dr Scheme编译是否不像VC一样调用函数时使用堆栈？
[解决办法]
想了一下觉得是不是因为递归每次需要调用两次函数（return Fibonacci(n - 1) + Fibonacci(n - 2)），需要的开销大，因而执行效率就低；但是对于迭代其实每次都调用的是一次函数（return Fibonacci_iter(a + b, a, count - 1)），相比较而言，迭代执行的效率就高一点啊。
以上是个人愚见，希望抛砖引玉，听听大家有什么好的想法没？继续关注此贴~~~
