algorithm - 为什么尾递归是递归的不好使用？

Question

我最近在学习日期结构。在 Mark Allen Weiss 的《C 语言中的数据结构和算法分析》一书中，为什么他说尾递归是递归的一种不好的用法，最好不要在第 3 章中使用它？但是我看到很多人说它在网上有用。

Answer 1

这不一定是坏事。尾递归始终等同于循环，显式编写循环可能更有效，具体取决于编译器。(*) 现代编译器（如 GCC）可以优化尾递归，但它们并不总是能识别它。当他们看不到它时，递归将消耗堆栈空间。

也就是说，诸如快速排序之类的算法自然是递归地表达的，它的两个递归之一是尾递归。如果我发现它太慢，我会在第一遍递归地编写它，然后将它重写为循环。

当一个算法只有一个尾递归的递归时，立即将其编写为循环可能仍然是一个好主意，因为递归函数比循环更难调试。

(*) 我假设我们只讨论 C。在其他一些语言中，尾递归既可以被认为是循环的自然方式（函数式语言），也可以被认为是一种彻头彻尾的厌恶（Python）。

Answer 2

尾递归很好，是一种非常有用的构建代码的技术。这并不“坏”。但是，有一些警告：

1. 像任何递归一样，除非您的编译器可以优化它（检查这个），否则它将消耗堆栈帧。对于大量输入，这可能会导致堆栈溢出。

2. 一些程序员对递归有一种幼稚的反感，并且知道尾递归总是可以转换为循环，相信它总是应该的。

由于上述两个原因，您应该学习如何在尾递归和循环之间进行转换，尤其是因为它可以帮助您了解编译器是否可以优化递归。