由于递归函数，理论函数堆栈的最大深度？

Question

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

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

在recurse(n)的执行过程中，理论堆栈最多有n个堆栈帧，因为[=12]不可能=] 位于 recurse(i) 之上，如果 0 <= k < i <= n，因为这意味着 recurse(i) 调用了 recurse(k)（基于函数体这是不可能的）。如果我的推理是正确的，那么最大深度一定是函数堆栈如下所示的情况：

Answer 1

这很容易证明。自己画出来 -

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)

这就是为什么 fib(n) for large n 不会溢出堆栈，而是长期占用你的 CPU 的原因。对于小的n比如n = 20，结果计算了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 循环，只需 1 帧，200 步即可完成。但这不是递归，所以在这个 post.

中可能不值得讨论

Answer 2

当 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)

由于递归函数，理论函数堆栈的最大深度？

Maximum depth of a theoretical function stack due to a recursive function?

recursion

stack

data-structures