c - 大量递归函数背后实际上发生了什么？

Question

我在下面有一个递归函数。

int f(int n){
  if(n<1) return 1;
  else return f(n-1) + f(n-1);
}

当我以较小的数字(例如f(0)，f(1)等)调用函数时，它可以正常工作。

但是当我调用 f(50)或 f(80)或 f(100)时，它只是等待并且没有输出显示。

我需要知道背后究竟发生了什么？

Answer 1

天真递归

维基百科定义的Recursion:

递归是以自相似的方式重复项目的过程。

您的程序正在求解数学recurrence relation:

f(n) = f(n - 1) + f(n - 1)

通过调用自身，将更大的 f(n)问题分解为越来越小的块，然后将这些问题分解为越来越小的块，依此类推。

当您调用 f(0)时会发生什么？因为在这种情况下，参数 n为零，所以您的基本情况被触发，并且递归链停止。这是非常简单的情况(与所有 n < 1一样):

    f(0)
     |
     1

f(1)怎么样？稍微复杂一点，但不多:

    f(1)
  /     \
f(0) +  f(0) = 1 + 1 = 2

让我们尝试一些更大的东西，例如 n = 5:

             _____________f(5)___________
            /                            \
        ___f(4)____        +        ____f(4)____
       /           \               /            \
    f(3)    +     f(3)     +     f(3)     +    f(3)
   /   \         /   \          /    \        /    \
f(2) + f(2) + f(2) + f(2)  +  f(2) + f(2) + f(2) + f(2)
/ \    / \     / \    / \      / \    / \    / \    / \
...    ...     ...    ...      ...    ...    ...    ... = f(0) * 32 = 1 * 32 = 32

...因此，事实证明，手工创建文本树非常令人讨厌。希望您现在就明白了。也许，您甚至已经发现了这种模式:

f(0) = 1
f(1) = 2
f(2) = 4
f(3) = 8
f(4) = 16
f(5) = 32
...

通常:

f(n) = 2ⁿ

从数学上讲，这是一个指数方程。用Big-O术语来说，这是一种在指数时间内运行的算法。用通俗易懂的术语来说，该算法确实太慢了。

考虑一下这里发生的一切:

进行的函数调用的数量随着输入的大小呈指数增长。哎哟!

该算法不仅会影响运行时间，而且空间复杂度也会受到影响。具有讽刺意味的是，您可能会在天真的递归中遇到的问题称为堆栈溢出，其中函数调用堆栈因大量函数调用而溢出，并且可用的堆栈空间实际上耗尽了。双!

该函数的时间和空间复杂度不仅随输入呈指数增长，而且该算法显然也完成了比所需更多的工作。每次执行f(n)并且未命中基本情况时，会发生什么情况？计算f(n - 1)，两次，。三重哎哟!

因此，很明显，该算法很糟糕。但是，该怎么办呢？

常见子表达消除

可以极大地加快程序运行速度的一种优化称为 common subexpression elimination。这是实现起来非常快速和简单的优化，并且消除了由朴素版本进行的绝大多数函数调用。您需要做的就是意识到:

return f(n - 1) + f(n - 1);

等效于此:

return 2 * f(n - 1);

这样您的代码将变为:

int f(int n)
{
    if(n < 1)
    {
        return 1;
    }

    else
    {
        return 2 * f(n-1);
    }
}

与原始版本并排运行此修订版，并被运行时之间的几个数量级差异所震惊!因为每次调用仅进行单个递归调用，所以指数算法实质上成为等效迭代方法的线性时间( O(n))直接向上递归版本。

太酷了吧？

附录:动态编程

尽管您的特定示例不需要动态编程，就像我最初认为的那样，但是在谈论递归时，这仍然是一个非常有用的话题，因此，我对本节进行了重新设计，使其比以前的设计更少。另外，这是部分附录，因为我将在下面使用 c++语法。我很抱歉，如果这让您不寒而栗，我只是不喜欢现在(也许将来……)重新实现 c++的 std::map的想法。

也许您听说过 dynamic programming。不，请不要畏缩!听起来很吓人，但事实并非如此。实际上，它非常棒!

简而言之，动态编程是一种蛮力的智能方法。 的想法是，您将 memoize先前计算的结果放入查找表中，以便在需要重新计算某些内容(以及某些算法的情况下，您正在执行 很多)的情况下，答案很简单常量时间( O(1)!)查找。

让我们以 Fibonacci sequence为例。斐波那契算法的标准，天真，常规的实现如下所示:

int fib(int n)
{
    if (n <= 1)
    {
        return n;
    }

    return fib(n - 1) + fib(n - 2);
}

上面是另一种指数时间( O(2ⁿ))算法。但是，优化该算法并不像以前那么简单，因为无法以完全相同的方式简化 fib(n - 1) + fib(n - 2)。但是，我们可以做的是添加一个数据结构，该结构旨在允许对程序预先访问预先计算的结果，并利用其避免大量的冗余计算。因此，优化的版本为:

long long fib_dp(int n)
{
    if (lookup.find(n) != lookup.end())
    {
        return lookup[n];
    }

    else if (n <= 1)
    {
        return n;
    }

    lookup[n] = fib_dp(n - 1) + fib_dp(n - 2);
    return lookup[n];
}

添加一个查找表(实现为 c++ std::map<int, long long>)，仅对tad进行逻辑调整，然后将普通的 int值替换为 long long值，您便拥有了一个Fibonacci算法版本，可以处理更大的值。 n， 更快。认真地，自己尝试一下并进行比较。天真的算法可能要花费数小时(或数天，甚至更多)才能完成，但动态编程版本却可以在几秒钟内完成。

所以...我希望所有这些都能回答您的问题(也许还有更多)。让我知道您是否还有其他人! :)

后续操作:只是为了让您真正理解未简化的表达式的效率低下-在我首次提交此问题的那一刻，我运行了该程序的两个版本(简化版本和天真的递归版本)，返回 n = 50的输入。我的台式机包含Intel i7-4770K，并且相关进程当前正在使用约13％的CPU处理能力。快速动态编程版本在几秒钟内完成了输出 1125899906842624。天真的递归版本在我输入时仍在工作，将近十二个小时。我想它将工作更长的时间(如果允许的话!)。

感谢吉姆·巴尔特(Jim Balter)所做的所有更正，并使我意识到动态编程很有用，但在这里完全没有必要!和往常一样，我使事情变得复杂得多。 OP并不是今天唯一在这里学习新知识的人! :)