我在下面有一个递归函数。
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)时，它只是等待并且没有输出显示。
我需要知道背后究竟发生了什么？
最佳答案
天真递归
维基百科定义的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并不是今天唯一在这里学习新知识的人! :)
关于c - 大量递归函数背后实际上发生了什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25221449/