c# - 这个天真的递归斐波那契实现如何不是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 堆栈帧的空间，不会占用任何明显的堆栈空间。