C尾递归优化

Question

我经常听到人们说C语言不支持尾调用消除。虽然标准没有保证，但在任何体面的实现中，它都能够被执行吗？假设你只关注成熟、良好实现的编译器，并且不关心对于为较为晦涩的平台编写的原始编译器的最大可移植性，那么在C语言中依赖尾调用消除是否合理？

此外，为什么标准将尾调用优化排除在外呢？

- dsimcha

---

相关链接：https://dev59.com/J0vSa4cB1Zd3GeqPie8o - Josh Lee

Answer 1

像 "C 不执行尾调用消除" 这样的说法是没有意义的。正如您自己正确地指出的那样，这取决于具体的实现方式。是的，任何合理的实现都可以将尾递归轻松转换成等效的循环。当然，C 编译器通常不会对每个代码片段进行什么优化和不优化的保证。您需要编译并自行查看。

- AnT stands with Russia

Answer 2

尽管现代编译器可能会在开启优化时进行尾调用优化，但您的调试构建可能会在没有它的情况下运行，以便您可以获取堆栈跟踪并逐步进入/退出代码等精彩功能。 在这种情况下，不需要尾调用优化。

由于尾调用优化并不总是可取的，因此强制编译器编写者使用它是没有意义的。

- Dobes Vandermeer

Answer 3

我认为，只有在预期或需要大量递归的语言中，即鼓励或强制使用函数式编程风格的语言中，才需要保证尾调用优化。在这些类型的语言中，您可能会发现for或while循环被强烈反对、被视为不雅，甚至完全不存在于该语言中，因此您将为所有这些原因（以及可能更多的原因）采用递归。

在我看来，C编程语言显然并没有考虑到函数式编程。有各种循环结构通常用于取代递归：for、do..while、while等。在这样的语言中，在标准中规定尾调用优化并没有太大意义，因为它并不严格要求保证程序的正常运行。

再与没有while循环的函数式编程语言进行比较：这意味着您将需要递归；这反过来又意味着，随着许多迭代，堆栈溢出将不会成为问题；因此，这种语言的官方标准可能会选择规定尾调用优化。

附言：请注意我提出尾调用优化的一个小缺陷。在末尾，我提到了堆栈溢出。但是谁说函数调用总是需要堆栈？在某些平台上，函数调用可能以完全不同的方式实现，而堆栈溢出甚至从未成为问题。这将是反对在标准中规定尾调用优化的另一个论据。（但别误解我的意思，即使没有堆栈，我也能看到这种优化的优点！）

- stakx - no longer contributing

---

无论如何实现，函数调用的一般情况总是需要保存并恢复一些状态。因此，总会有一些函数，太多的嵌套函数调用会填满可用于存储此状态的内存。传统的数据结构是在一个固定内存块中使用堆栈，但也可以用其他方式实现。尾递归消除可以避免某些函数的保存和恢复，但两次调用自身的非平凡函数仍需要为第二个调用存储状态。 - jilles

@jilles：没错，尾调用优化应该有助于保留内存，无论函数调用如何工作。然而，CPU堆栈的一个特点是它的容量通常相对有限；比如堆内存更加有限。这就是为什么我提到了堆栈溢出，但没有提到更一般的内存不足情况；我假设你需要进行几乎难以置信的递归才能耗尽例如2GB的内存。 - stakx - no longer contributing

Answer 4

回答你的最后一个问题：标准绝对不应该对优化做任何声明。在某些环境下，实现优化可能更加困难或容易。

- Frank

---

标准要求 while 循环在常数内存下运行（除了在循环中分配的内存），这样做是否合适？标准要求尾递归函数在常数内存下运行，这样做是否合适？ - Jules

我认为Scheme需要尾调用优化，但Scheme是一种主要使用递归作为控制结构的函数式语言。 C程序往往不太递归，并且有常用的迭代结构。 - David Thornley

在哪种环境下，尾调用优化会“更难实现”？我看不出环境会有任何影响，因此我已经暂时投了反对票。 - Mark Amery

@MarkAmery +1，尾递归优化在C++中只会捣乱析构函数，但在C中在基本上任何环境下都是绝对没问题的——甚至在某些情况下还可以减少堆栈占用。 - Paul Stelian

Answer 5

如果你喜欢通过构造证明，这里有一个漂亮的尾递归优化和内联的godbolt示例：https://godbolt.org/z/DMleUN。

然而，如果你将优化提高到 -O3（或者毫无疑问地等待几年或使用另一个编译器），优化将完全删除循环/递归。

这是一个示例，即使使用 -O2 也可以优化为单个指令：https://godbolt.org/z/CNzWex。

- Evan Benn

Answer 6

语言标准定义了语言的行为方式，而不是编译器必须实现的方式。优化并非强制要求，因为并不总是需要。编译器提供选项，以便用户可以启用优化，如果他们需要的话，也可以关闭它们。编译器优化可能会影响调试代码的能力（变得更难以逐行匹配 C 和汇编），因此只在用户请求时执行优化是有意义的。

- bta

---

要求符合特定要求的调用模式使用常量内存空间非常容易。这是语言行为的一部分，也影响着程序是否能够进行数百万次尾递归调用而不返回（就像我写的一个依赖于编译器TCO的程序）。 - Jimmy Hartzell

Answer 7

有些情况下，尾调用优化可能会破坏ABI或者至少很难以保持语义一致的方式实现。比如，考虑共享库中的位置无关代码：某些平台允许程序在动态链接库之间进行动态链接，以便在多个不同的应用程序都依赖于相同功能时节省主存储器。在这种情况下，库只加载一次，并映射到每个程序的虚拟内存中，就好像它是系统上唯一的应用程序一样。在UNIX和一些其他系统上，可以通过使用位置无关代码来实现这一点，因此寻址是相对于偏移量而不是绝对于固定地址空间的。然而，在许多平台上，位置无关代码不能进行尾调用优化。问题在于，用于导航程序的偏移量必须保存在寄存器中；在Intel 32位上，使用了被调用方保存的寄存器%ebx；其他平台也遵循这个想法。与使用普通调用的函数不同，使用尾调用的函数必须在跳转到子例程之前恢复被调用方保存的寄存器，而不是在返回自己时恢复。通常，这没有问题，因为在这个点上，最顶层的调用函数不关心%ebx中存储的值，但是位置无关代码依赖于每个跳转、调用或分支命令中这个值。

其他问题可能涉及面向对象语言（如C++）中未完成的清理工作，这意味着函数中的最后一次调用实际上并不是最后一次调用，而是清理工作。因此，编译器通常在这种情况下不会进行优化。

当然，setjmp和longjmp也是有问题的，因为这实际上意味着一个函数可以执行多次，而不是只执行一次。这在编译时很难或不可能进行优化！

可能还有更多技术原因可以考虑。这些只是一些注意事项。

- nondeterministic

Answer 8

编译器通常可以识别函数在调用另一个函数之后不需要执行任何操作的情况，并将该调用替换为跳转。许多可以安全执行此类操作的情况很容易识别，并且这些情况符合“安全的低挂果”标准。然而，即使在可以执行此类优化的编译器上，什么时候应该或将会执行此项优化也不总是明显的。各种因素可能使尾调用的成本大于普通调用的成本，并且这些因素可能不总是可预测的。例如，如果一个函数以return foo(1,2,3,a,b,c,4,5,6);结尾，则将a、b和c复制到寄存器中，清除堆栈并准备传递参数可能是可行的，但可能没有足够的寄存器来处理foo(a,b,c,d,e,f,g,h,i);。

如果一种语言有一个特殊的“尾调用”语法，要求编译器在任何可能的情况下都进行尾调用，并拒绝编译否则，代码就可以安全地假设这样的函数可以任意嵌套。然而，在使用普通调用语法时，没有一般方法可以知道编译器是否能够更便宜地执行尾调用而不是“普通”调用。

- supercat