堆栈中将存储多少调用？

Question

谁能解释一下下面的递归方法将在堆栈中存储多少次调用，为什么？什么时候存储在堆栈中？显然是 49 次调用，但我不明白为什么。谢谢。

public static long fib( int n ){ // n = 50
    if( n <= 1 )
        return 1;
    else
        return fib( n - 1 ) + fib( n - 2 );
    }

Answer 1

堆栈中对 fib 的调用次数是 fib 需要被调用计算的次数 fib(n)。

fib(50) 将调用 fib 函数超过 49 次。

举个小例子。如果您调用 fib(3)，这将调用 fib(2) 和 fib(1)。 fib(2) 将调用 fib(0) 和 fib(1)。这已经是 fib(3) 的 5 次 fib 调用。

对于较大的 n 值，每次调用 fib(3) 将导致总共调用 5 次，因为这些值未存储在任何地方。 fib 求值的唯一方法是为两个较小的值调用自身。

斐波那契数列是错误使用递归的标准示例，因为成本是指数级的。我会让你算出到底需要多少电话。

Answer 2

下面的递归方法将在堆栈中存储多少次调用，为什么？

输入为 50，在任何给定时刻，包括对 fib 的初始调用在内，堆栈帧的最大数量将为 50。（因此最多将有 49 个递归调用存储在在任何给定时刻堆叠）。

最多可以有 50 个堆栈帧的原因是：

对fib(50)的初始调用是1个堆栈帧。

然后用这个语句，return fib( n - 1 ) + fib( n - 2 ); 对左侧 fib 的递归调用将首先执行，将 fib(49) 放入堆栈。我们将再次点击 return 行，将 fib(48) 放入堆栈。这将重复，直到 fib(1) 在堆栈中命中 return 1; 语句。这会将 return 变为 fib(2) 并允许在语句 return fib( n - 1 ) + fib( n - 2 ); 中执行正确的递归调用。

长话短说，所有左递归调用甚至在 1 个右递归调用之前执行。所以很容易看出最后一次递归调用会有 fib(50)、fib(49)、...，最后是 fib(1)，导致执行 [= 时最多有 50 个堆栈帧23=].

什么时候存储在堆栈中？

当你调用一个函数时，一个栈帧被分配，在函数returns之后，栈帧被释放。甚至 main 的函数调用也存储在堆栈中。然而，堆栈框架可能会被优化掉，但这是一个更高级的话题。

如果您想了解更多有关堆栈帧优化的信息，请参阅我小时候问过的这个问题：

Does a stack frame really get pushed onto the stack when a function is called?

补充编辑：如果您想通过视觉了解递归是如何发生的，请将您的手指放在根的顶部，然后首先沿着左侧沿着树的外部追踪：

Answer 3

将堆栈框架想象成您发送给您以获取一些信息的人类工作者。暂时忘掉斐波那契数列，想想一个更简单的递归公式，求和。

int sum(int n) {
  if (n == 1) {
    return 1;
  } else {
    return sum(n - 1) + n;
  }
}

sum(1) = 1

sum(2) = sum(1) + 2 = 1 + 2 = 3

等...

现在想象一下，当您调用 sum(n) 时，您会派人去为您查找结果。在他给你你要求的结果之前，他不会 "finished" 工作。但是，他还需要调用 sum(n - 1)，这只能通过让另一个人工作来完成。现在我们有两个人同时工作！您要问的问题是 同时工作的最大人数是多少？ 如果您包括您自己，对于上面实施的求和算法和实施斐波那契数列。

堆栈中将存储多少调用？

How many calls will be stored in stack?

java

recursion

stack

fibonacci