有人可以解释一下下面的递归方法将在堆栈中存储多少次调用，为什么？什么时候存储在堆栈中？显然是 49 次调用，但我不明白为什么。谢谢。
public static long fib( int n ){ // n = 50
if( n <= 1 )
return 1;
else
return fib( n - 1 ) + fib( n - 2 );
}
最佳答案
对于下面的递归方法，堆栈中将存储多少次调用，为什么？
输入为 50，在任何给定时刻，包括对 fib 的初始调用在内，堆栈帧的最大数量将为 50。(因此最多将存储 49 个递归调用堆栈在任何给定时刻)。
最多可以有 50 个栈帧的原因是:
fib(50) 的初始调用是 1 个堆栈帧。
然后用这个语句，return fib( n - 1 ) + fib( n - 2 );
左边对 fib 的递归调用将首先执行，将 fib(49) 放入堆栈。我们将再次点击返回行，将 fib(48) 放入堆栈。这将重复，直到 fib(1) 在堆栈中命中 return 1; 语句。这将返回到 fib(2) 并允许在语句 return fib( n - 1 ) + fib( n - 2 ); 中执行正确的递归调用。
长话短说，所有左递归调用甚至在 1 个右递归调用执行之前执行。所以很容易看出您将拥有 fib(50)、fib(49)，...，最后是 fib(1)对于最后一个递归调用，在执行 fib(50); 时导致最多 50 个堆栈帧。
什么时候存储在堆栈中？
调用函数时，会分配一个栈帧，函数返回后，会释放栈帧。甚至 main 的函数调用也存储在堆栈中。然而，堆栈框架可能会被优化掉，但这是一个更高级的话题。
如果您想了解更多有关优化堆栈框架的信息，请参阅我小时候问过的这个问题:
Does a stack frame really get pushed onto the stack when a function is called?
补充编辑:
如果您想通过视觉了解递归是如何发生的，请将您的手指放在根的顶部，然后首先沿着左侧沿着树的外部追踪:
关于java - 堆栈中将存储多少调用？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28711521/