由于递归函数而导致理论函数堆栈的最大深度?

Question

如果我们有一个永远不会满的理论堆栈内存，并且我们有一个简单的递归函数

recurse(n):
if n > 0:
recurse(n-1)
recurse(n-2)
return

论证理论栈在执行recurse(n)的任何时候最多有n个栈帧是否合理，因为如果0 <= k<= n，recurse(k)不可能在recurse(i)之上，因为这意味着recurse(i)称为recurse(k)(根据函数体，这是不可能的)。如果我的推理是正确的，那么当函数堆栈如下所示时，最大深度必须是这种情况：

(BOTTOM-MOST)|recursion(n)|recursion(n-1)|...|recursion(2)|recursion(1) (TOP-MOST)

Answer 1

当n = 0函数调用本身有一个堆栈帧时 - 任何n的堆栈帧都不能少于一个 - 因此最大堆栈帧数的公式是max(1, n+1)，而不是n确切。否则你的推理是正确的，这个公式可以用归纳法证明：

• 在基本情况下，当n <= 0时，有一个堆栈帧，它等于max(1, n+1)因为n+1 <= 1。
• 否则，当n >= 1时，会进行两个递归调用，一个堆栈深度为max(1, n)，另一个堆栈深度为max(1, n-1)归纳假设。因此，最大堆栈深度(包括调用n的当前堆栈帧)等于1 + max(max(1, n), max(1, n-1))。这可以简化为1+n，因为n是max操作数中最大的操作数，并且1+n根据需要等于max(1, n+1)。

Answer 2

这很容易证明。自己规划一下——

recurse(0)

recurse(1)
recurse(0)
recurse(-1)

recurse(2)
recurse(1)
recurse(0)
recurse(-1)
recurse(0)

recurse(3)
recurse(2)
recurse(1)
recurse(0)
recurse(-1)
recurse(0)
recurse(1)
recurse(0)
recurse(-1)

recurse(4)
recurse(3)
recurse(2)
recurse(1)
recurse(0)
recurse(-1)
recurse(0)
recurse(1)
recurse(0)
recurse(-1)
recurse(2)
recurse(1)
recurse(0)
recurse(-1)
recurse(0)

这就是为什么大型nfib(n)不会溢出堆栈，而是长时间占用 CPU 的原因。对于n = 20等小n，结果以 1,048,576 步计算，但仅使用 20 帧 -

function fib(x)
{ if (x < 2n)
return x
else
return fib(x - 1n) + fib(x - 2n)
}
console.log("result %s", fib(20n))
// result 6765

对于像n = 200这样的较大n，需要惊人的 1,606,938,044,258,990,275,541,962,092,341,162,602,522,202,993,782,792,835,301,376 次计算，但只有 200 的堆栈深度，不会导致溢出。然而，即使每秒 1,000,000,000 次计算，也需要 50,955,671,114,250,072,156,962,268,275,658,377,807,020,642年才能完成 -

function fib(x)
{ if (x < 2n)
return x
else
return fib(x - 1n) + fib(x - 2n)
}
console.log("result %s", fib(200n))
// result ...

如果你试图运行上面的fib(200)，JavaScript 将导致你的浏览器挂起，直到太阳死后很久。刷新此选项卡，我们可以在1 毫秒内计算出答案。这种重写fib使用线性递归，计算n = 200只需要 200 步和 200 帧 -

function fib(x, a = 0n, b = 1n)
{ if (x == 0n)
return a
else
return fib(x - 1n, b, a + b)
}
console.time("fib(200)")
console.log("result %s", fib(200n))
console.timeEnd("fib(200)")
// result 280571172992510140037611932413038677189525
// fib(200): 1.000ms

如果使用while循环，则可以在 200 个步骤和 1 帧内完成。但这不是递归，所以也许不值得在这篇文章中讨论。