堆栈中将存储多少个调用？

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

对于下面的递归方法,将在堆栈中存储多少个调用,为什么？

输入为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)是最后的递归调用,在执行时最多导致50个堆栈帧fib(50);.

什么东西准确存储在堆栈中？

调用函数时,将分配堆栈帧,并在函数返回后,释放堆栈帧.甚至函数调用main都存储在堆栈中.但是,堆栈帧可能会被优化掉,但这是一个更高级的主题.

看到这个问题,当我想了解更多关于优化堆栈帧的信息时,我问我什么时候是小伙伴:

在调用函数时,堆栈帧是否真的被压入堆栈？

附加编辑:如果您想了解如何通过视觉进行递归,请将手指放在根的顶部,并首先在左侧的树的外侧追踪: