斐波那契计算时间

递归式斐波那契与循环式斐波那契之间是否存在明显的计算时间差异？我使用递归将斐波那契数列运行到 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) );
};

For-Loop解决方案：

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;
};

与尾递归和迭代版本相比，传统的递归方法非常慢。在下面的迭代版本示例代码中，使用展开循环以及达夫的装置 http://en.wikipedia.org/wiki/Duff%27s_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

为了解释这里的逻辑，对于 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;
}