c - 为什么C、Pascal等语言不能实现尾递归？

Question

我正在阅读 SICP .它在 footnote 之一中提到那:

Making a compiler generate tail-recursive code might seem like a straightforward idea. But most compilers for common languages, including C and Pascal, do not do this, and therefore these languages cannot represent iterative processes in terms of procedure call alone. The difficulty with tail recursion in these languages is that their implementations use the stack to store procedure arguments and local variables as well as return addresses.

---

我无法理解为什么如果堆栈用于过程参数、局部变量和返回地址，则无法实现尾递归。

Answer 1

C当然可以实现尾递归。 C 中的尾递归如下所示:

int foo (int bar)
{
    int baz;
    ...
    return foo(baz);
}

所有 C 编译器都可以做到这一点。其中一些(实际上是大多数)为它提供了优化，因此它不使用额外的堆栈空间，像这样(gcc、MSVC 和 clang/LLVM):

• How do I check if gcc is performing tail-recursion optimization?
• Which, if any, C++ compilers do tail-recursion optimization?
• http://llvm.org/docs/CodeGenerator.html#tail-call-optimization

我不太了解 Pascal，但这里有一个 2004 年支持尾递归的非基于 LLVM 的 pascal 编译器的引用:

• http://en.wikipedia.org/wiki/Free_Pascal#Consolidation:_the_2.2.x_release_series

考虑到 LLVM 案例适用于多种语言并且可能是最常见的现代编译器后端，并且考虑到这些是最常见的 C 编译器，并且考虑到您的源代码似乎没有区分尾递归和不使用堆栈空间的尾递归，我建议您的来源是错误的或至多是过时的。

关于你问题的第二部分:

I'm unable to understand why it is not possible to implement tail recursion if stack is used for procedure arguments, local variables and return addresses.

它是可以使用堆栈实现尾递归，就像任何其他递归一样。但是，如果您不对其进行优化以不使用堆栈(例如上面的链接)，那么深度递归将导致您耗尽堆栈空间。可以说，在内存便宜且堆栈大小不受 32 位内存映射限制的现代环境中，这不是什么大问题。然而，考虑到大多数编译器会优化并且无论如何都可以避免堆栈，它也适用于其他更具挑战性的环境。