recursion - 限制实现 TCO 的语言中尾递归的递归深度？

Question

在实现尾调用优化的语言中，递归深度的理论/实践限制是什么？（请假设循环函数被正确地尾调用）。

我的猜测是理论上的限制是 NONE，因为没有递归过程，即使它是递归过程。实际限制将是可用的主存储器允许使用的限制。如果我在某处错了，请澄清或更正。

score 3 · Accepted Answer

当尾递归函数被优化时，它本质上会变成一个迭代函数。编译器将原始调用的堆栈帧重用于后续调用，因此您不会用完堆栈空间。如果您没有分配任何堆内存（或任何其他不在堆栈上的内存，就此而言），您可以拥有无限深（只要您有足够的耐心；））递归（将其视为无限循环；它具有相同的特性）。

总而言之，没有实际限制。

score 1 · Accepted Answer

除了@Mehrdad Afshari 写的内容之外，我只想指出，尾递归（或更一般地说，尾调用链）可能是无限的，因为否则您无法编写 Web 服务器，这实际上非常重要，操作系统、解释器、REPL 或函数式语言中的任何类型的事件处理循环。

毕竟，操作系统不过是一个无限循环，而用函数式语言编写循环的方法就是使用尾递归。如果尾递归不是无限的，那么循环就不会是无限的。因此，您不仅不能编写操作系统，而且该语言甚至都不是图灵完备的。

基本上，这就是您使用函数式语言编写 Web 服务器的方式：

def loop(queue) = {
  // handle first request in queue
  loop(queue)
}

如果没有无限尾递归，这将很快耗尽内存。

2 回答 2