c++ - 递归函数是否比非递归函数慢

Question

我对数字的阶乘和斐波那契数列(在 C++ 中完成)使用了递归函数，我发现关于阶乘的递归函数运行正常，执行速度与预期相差不大。

然而，在斐波那契数列上，它绝对是缓慢的。为什么会这样？

递归方法:

unsigned long int fib_num(int n)  //This is My code
{
    switch (n)
    {
    case 1:
        return 0;
        break;
    case 2:
        return 1;
        break;
    default:
        return fib_num(n - 1) + fib_num(n - 2);
        break;
    }
}

迭代方法:

first = 0;
second = 1

for(i = 0; i < num; i++)   
{
    cout<<"\n"<<first;

    next = first + second;

    first = second;
    second = next;
}

Answer 1

你的观察是正确的，递归方法计算，在这种情况下，斐波那契数，如果你仔细看结果从一开始就计算斐波那契的每一项，即

例如，要计算 F[n] + F[n-1]，函数会分别计算这两项，并多次执行相同的工作。

例子:F[5] = F[4] + F[3]

要计算 F[3] :程序计算:F[2]、F[1]、F[1]、F[0]

要计算 F[4]:程序再次计算:F[2]、F[2]、F[1]、F[1]、F[0]、F[0] 和 F[3]

以下是您的函数调用的图形化形式:

这导致您观察到，即在每次递归调用时，工作量加倍，导致复杂度为:O(2ⁿ)。

---

避免上述情况的一种可能方法是使用内存:

// header needed for the container: map
#include <map> 

int mem_fact (int i, std::map<int, int>& m)
{
    // if value with key == i does not exist in m: calculate it
    if (m.find(i) == m.end()) 
    {
        // the recursive calls are made only if the value doesn't already exist
        m[i] = mem_fact (i - 1, m) + mem_fact (i - 2, m); 
    }

    // if value with key == i exists, return the corresponding value
    return m[i];
}

int fast_factorial (int i)
{
    // key (Fibonacci index) - value (Fibbonaci number)
    std::map<int, int> memo;

    // initialize the first two Fibonacci numbers
    memo.insert(std::pair<int,int>(0, 0));
    memo.insert(std::pair<int,int>(1, 1));

    return mem_fact(i, memo);
}

注意:在main()中需要调用fast_factorial(num_of_fib);