c - GCC 迭代函数优化

Question

我有以下递归和迭代版本的斐波那契代码:

#include <stdio.h>

typedef long long INT;

long long recursive (long long i) {
    if (i == 0) return 0;
    if (i == 1) return 1;
    return recursive (i-1) + recursive (i-2);
}


long long iterative (long long i) {
    INT counter = i-1;
    INT fib1 = 0;
    INT fib2 = 0;

    // first iteration
    fib1 = 0;
    fib2 = 1;

    while (counter > 0) {
        INT temp1 = fib1;
        INT temp2 = fib2;
        fib1 = fib2;
        fib2 = temp1 + temp2;

        counter--;
    }

}

int main (int argc, char **argv) {

    printf("Result: %lli\n", iterative(10));

    return 0;
}

我尝试使用 GCC -O2 优化来编译它，看看递归是否会比迭代执行得更好，但我注意到一个有趣的现象:当使用 -O2 编译时，迭代函数输出 0，而如果它是在没有标志的情况下编译的，它会输出正确的数字。

gcc -O2 fibonacci.c -o fib && ./fib: 结果:0

gcc fibonacci.c -o fib && ./fib: 结果:55

Answer 1

递归将比迭代或尾递归版本慢(通常会优化为迭代版本)。两者的示例都在此线程中:

Fibonacci Computation Time