为什么像C,Pascal这样的语言不能实现尾递归？

Question

我在读SICP.其中一个脚注中提到:

使编译器生成尾递归代码似乎是一个简单的想法.但是大多数常用语言编译器(包括C和Pascal)都没有这样做,因此这些语言不能仅仅根据过程调用来表示迭代过程.这些语言中尾递归的难点在于它们的实现使用堆栈来存储过程参数和局部变量以及返回地址.

---

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

Answer 1

C当然可以实现尾递归.C中的尾递归看起来像这样:

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

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

• 如何检查gcc是否正在执行尾递归优化？
• 哪个(如果有的话)C++编译器会进行尾递归优化？
• 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编译器,并且鉴于您的源代码似乎不区分尾递归和尾递归而不使用堆栈空间,我' d建议您的来源错误或最多过时.

问题的第二部分:

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

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

Answer 2

这些语言中尾递归的难点在于它们的实现使用堆栈来存储过程参数和局部变量以及返回地址.

在机器语言中,没有函数调用,因此函数调用被转换为

1. 将参数推入调用堆栈
2. 将返回地址压入堆栈
3. 转到要调用的子例程的主体
4. 当子程序退出时,它会返回到我们之前推送到堆栈的返回地址
5. 参数从堆栈中删除

现在这个"调用约定"模式有两个基本变体,与谁负责第5步(从堆栈中删除函数参数)有关.在C中,调用约定是函数调用者负责清理堆栈.这允许可变参数函数printf(在这些情况下,只有调用者知道在调用完成后弹出的正确参数数量),但意味着你不能进行尾调用优化,因为"返回"不是函数的最后一件事(你之后仍然需要清理堆栈).另一方面,如果您的调用约定是让函数本身清理堆栈,那么您将失去具有可变参数函数但能够具有TCO的能力.