这个天真的递归fibonacci实现怎么没有stackoverflow？

Question

几个月前,作为一个笑话,我的一位同事试图通过使用这种指数算法计算斐波纳契数来"加速宇宙的热死":

int Fib(int n)
{
    if (n <= 1)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

这怎么不会导致C#中的stackoverflow？我们设法在放弃之前得到了Fib(52)(而Fib(51)花了很多时间).我认为这会严重破坏堆栈以导致堆栈溢出,因为CLR默认只将1M分配给堆栈.另外,我很确定这也不适合尾递归.

Answer 1

递归调用不是同时计算的,而是顺序Fib(n - 2)计算的,这意味着只会在Fib(n - 1)(或相反)之后计算.这意味着即使您创建2^n递归调用,也只会n同时处于活动状态.因此, Fib(52)只需要堆栈52帧的空间Fib,这不占用任何明显的堆栈空间.