大数字的递归函数背后究竟发生了什么？

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

天真的递归

维基百科定义的递归:

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

你的程序正在解决数学递归关系:

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术语中,这是一种在指数时间内运行的算法.用更通俗的术语来说,这个算法真是太神了.

想想这里发生了什么:

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

2. 算法的运行时间不仅受到影响,空间复杂度也受到影响.具有讽刺意味的是,您可能会遇到的天真递归问题被称为堆栈溢出,其中函数调用堆栈溢出了大量的函数调用,并且可用堆栈空间基本耗尽.双!

3. 不仅此功能的时间和空间复杂度成倍与输入增长,算法也很清楚这样做的方式更多的工作比它需要.每次f(n)执行的事情都会被执行而基本案例没有被击中？f(n - 1)算了两次.三重!

所以,很明显这个算法糟透了.但是可以做些什么呢？

常见的Subexpression消除

一种优化是去一个长向加快你的程序运行时的方式被称为公共子表达式消除.这是一个非常快速和简单的优化实现,它消除了天真版本所做的绝大多数函数调用.你需要做的就是意识到这一点:

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在时刻(也许在未来的...).

也许你听说过动态编程.不,请不要畏缩!这听起来很可怕,但事实并非如此.实际上,它非常棒!

简单地说,动态编程是一种蛮力的智能方法.这个想法是你将先前计算的结果记忆到查找表中,以便在你需要重新计算某些东西的情况下(和一些算法,你做了很多),答案只是一个恒定的时间(O(1)!)查找.

我们以斐波纳契数列为例.Fibonacci算法的标准,天真,普通的实现如下所示:

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>),调整的逻辑只是一点点,而且换出普通老式int的值long long值,你已经拥有属于自己的版本,斐波那契数的算法,可以处理更大的价值n,远快.说真的,亲自试试并比较一下.天真算法可能花费数小时(或数天或更长时间)来完成,动态编程版本可以在几秒钟内完成.

所以...我希望所有这些都回答了你的问题(也许更多).如果您有其他人,请告诉我!:)

后续行动:只是为了把你的非简化表达式的效率降低到正常水平 - 就在我第一次提交这个问题的时候,我运行了这个程序的两个版本(简化版和天真的​​递归版)回到 -回到输入n = 50.我的桌面包括Intel i7-4770K,相关流程目前使用的CPU占处理能力的13%左右.快速动态编程版本在几秒钟内完成,输出为1125899906842624.在接近十二个小时之后,天真的递归版仍在我打字时工作.我想它会工作更长时间(如果我允许的话!).

感谢Jim Balter的所有更正,并让我意识到动态编程很有用,但这里完全没有必要!像往常一样,我做的事情比他们需要的要复杂得多.OP不是今天在这里学习新东西的唯一人!:)