为什么函数 fib2 比函数 fib 和 fib3 快得多？

Question

下面的C代码，为什么函数

fib2

比函数

fib

和

fib3

快很多？

编译：

gcc -O3 main.c -o main

海湾合作委员会版本：

gcc (GCC) 10.2.1 20200825 (Alibaba 10.2.1-3.6 2.32)
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE

输出：

-298632863    fib Time spent: 23.668928 seconds
-416927699    fib2 Time spent: 2.302187 seconds   // Why faster？
-298632863    fib3 Time spent: 24.243148 second

代码：

#include <stdio.h>
#include <time.h>

long long fib2(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        long long first = fib2(n - 1);
        long long second = fib2(n - 2);
        return first * first + second * second;
    }
}

int fib(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        return fib(n - 1) + fib(n - 2);
    }
}

long long fib3(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        long long first = fib3(n - 1);
        long long second = fib3(n - 2);
        return first + second;
    }
}

void main()
{
    clock_t start1 = clock();
    printf("%d", fib(50));
    clock_t end1 = clock();
    double time_spent1 = (double)(end1 - start1) / CLOCKS_PER_SEC;
    printf("fib Time spent: %f seconds\n", time_spent1);
    printf("%d", fib2(50));
    clock_t end2 = clock();
    double time_spent2 = (double)(end2 - end1) / CLOCKS_PER_SEC;
    printf("fib2 Time spent: %f seconds\n", time_spent2);
    printf("%d", fib3(50));
    clock_t end3 = clock();
    double time_spent3 = (double)(end3 - end2) / CLOCKS_PER_SEC;
    printf("fib3 Time spent: %f seconds\n", time_spent3);
}

Answer 1

这三种处理功能之间的比较从一开始就是不公平的。例如，当我用第 40 个斐波那契数进行测试时，结果完全相反（fib2 的处理时间更长）。

102334155  fib Time spent: 0.401000 seconds
1059467309 fib2 Time spent: 0.815000 seconds
102334155  fib3 Time spent: 0.423000 seconds

另一方面，在我看来，对较大数字的计算会导致更长的处理时间：

• 在 fib 和 fib3 函数之间，如果结果是 int 范围内的小斐波那契数，则计算时间将相同。但是，如果数字较大，fib 只会产生 int 结果，而 fib3 返回 long long 类型，需要更多的计算工作。

• 无法将fib2与fib和fib3进行比较，因为它们的递归公式不同； fib2 总是使用更多的计算。可能是因为 fib2 每次计算后的结果由于频繁溢出而小得多，所以处理时间看起来更快，但这当然只是一种幻觉。