c - 为什么递归需要这么长时间？

Question

在使用递归计算斐波那契数列的第n个数时，我写了这个简单的程序:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

unsigned int long long fibonacci(unsigned int number);

//game of craps
int main(int argc, char** argv)
{

    for(int n = 1; n <= 100; n++)
    {
        printf("%llu\n", fibonacci(n));
    }

    return (EXIT_SUCCESS);
}


unsigned long long int fibonacci(unsigned int number)
{
    if (number == 0 || number == 1)
    {
        return number;
    }
    else
    {
        return fibonacci(number - 2) + fibonacci(number - 1);      
    }
}

其中每次调用序列中的 n+1 数字都会使程序必须运行的函数调用次数加倍。因此，对递归函数的调用次数是 2^n，或指数复杂度。明白了。但是所有的计算能力都去了哪里呢？一旦序列中的第 n 个数字开始达到 40，计算机开始花费大量时间来计算结果，在 n = 47 时需要 30 多秒。但是我的电脑显示我只使用了 21% 的 CPU 功率。我正在使用 NetBeans IDE 来运行该程序。这是一个四核系统。

Answer 1

the number of calls being made to the recursive function is something of 2^n, or exponential complexity. Understood.

我不确定您是否完全理解这一点，因为您似乎对它在 n=40 和 n=47 时变得如此缓慢感到惊讶。

如果复杂度为 2^n，n 为 40，则为 2⁴⁰，或 1,099,511,627,776，或大约 1 万亿 操作。如果您的计算机每纳秒可以运行其中一个操作，即每秒 10 亿次操作，则需要 1000 秒才能完成。

考虑一下 n 是否只有 30。2³⁰ 是 1,073,741,824，这在同一台计算机上只需要大约 1 秒。

如前所述，您只使用了一个内核。您可以并行化，但这无济于事。使用四个内核而不是一个内核，我的 n=40 示例仍然需要 250 秒。上升到 n=42，你又回到了 1000 秒，因为并行化充其量会使你的性能成倍增加，但像这样的算法呈指数级增长。