c# - 这种天真的递归斐波那契实现如何不是stackoverflow？

Question

作为几个月前的一个笑话，我的一位同事试图通过使用这种指数算法计算斐波那契数来“加速宇宙的热寂”：

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

这如何不会导致 C# 中的堆栈溢出？我们在放弃之前设法到达了 Fib(52)（而 Fib(51) 花了很多时间）。我认为这会严重影响堆栈​​以导致堆栈溢出，因为默认情况下 CLR 仅分配 1M 给堆栈。另外，我很确定这也不符合尾递归的条件。

Answer 1

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

Answer 2

朴素的斐波那契实现确实会产生大量的函数调用（实际上等于结果），但它不会递归得很深。递归的最大深度是n。