递归函数是否比非递归函数慢？

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

- Suhrid Mulay

---

抱歉，我们不是能够立即确定为什么一段代码比另一段代码慢的心灵读者，未经查看所有相关代码。 - Sam Varshavchik

不，递归函数本质上并不慢。如果你想知道为什么这两个函数的性能不同，你就必须展示它们。 - JJJ

递归斐波那契可能会很慢，因为你要递归两次，每次都重新计算整个前面的数列。迭代的斐波那契只看已经计算出来的前面两个值，不需要每次都回到开头重新计算。 - Barmar

fib_num(5) 会发出两个调用。他们各自会再次发出两个调用，以此类推，直到最终到达递归的基础部分。因此，每一层都会使调用数量翻倍，这使得时间复杂度为O(2^n)。 - Barmar

@Barmar。啊，好的。该函数被调用直到满足情况1和2的条件。由于它被调用两次，一次是(n-1)，另一次是(n-2)，因此它的形状将为2^n。这使得它比for循环更加资源密集。我的推理正确吗？ - Suhrid Mulay

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^n)。

---

一种避免上述情况的可能方式是使用记忆化技术：

// 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)函数；

- Ziezi

Answer 2

我将给出一个斐波那契数列的例子。

recursive 41 index calculated pass time 1.343 seconds
non recursive 40000 index calculated pass time 1.042 seconds

这是输出的代码。

public static void main(final String[] args) {

    long before = new Date().getTime();
    for(int i = 0; i <= 41; i++) {
        findRecursiveFibionacci(i);
    }
    System.out.println("recursive 41 index calculated pass time "+((float)(new Date().getTime()-before)/1000) + " seconds");

    long before2=new Date().getTime();
    for(int i = 0; i <= 40000; i++) {
        getFib(i);
    }
    System.out.println("non recursive40000 index calculated pass time "+((float)(new Date().getTime()-before2)/1000) + " seconds");
}

public static long getFib(final int index) {
    long a=0,b=0,total=0;
    for(int i=0;i<= index;i++) {
        if(i==0) {
            total=a+b;
            a=0;
        }else if(i==1) {
            b=1;
            total=a+b;

        }else if(i%2==0) {
            total=a+b;
            a=total;
        }else {
            total=a+b;
            b=total;
        }
    }
    return total;
}

public static long findRecursiveFibionacci(final int a ){
    if(a==0)return 0;
    if(a<=2)return 1;
    final long fibterm = findRecursiveFibionacci(a-1)+findRecursiveFibionacci(a-2);
    return fibterm;
}

- Emre Kilinc Arslan