尾递归为什么不适合使用递归？

Question

我最近在学习数据结构。在Mark Allen Weiss的书《数据结构与算法分析（C语言版）》中，为什么他在第三章中说尾递归是递归的不良用例，最好不要使用呢？但是我在网上看到很多人说它很有用。

- user2765571

---

除非你使用的编程语言必须通过递归来实现循环，否则没有什么理由使用尾递归，因为你总是可以将其扩展为循环。 - nhahtdh

Answer 1

这不一定是坏事。尾递归总是等价于循环，明确写出循环可能更有效率，具体要看编译器的表现。（*）现代编译器如GCC可以消除尾递归，但并不总能识别它。如果编译器未能识别，递归会占用栈空间。

话虽如此，像快速排序这样的算法自然而然地被表达成递归形式，并且其中两个递归之一是尾递归。如果执行效率太低，我会首先使用递归方式编写它，然后将其改写为循环。

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

（*）我假设我们只谈论C语言。在其他一些语言中，尾递归可能被视为循环的自然方式（函数式语言），或被认为是彻底的败笔（Python）。

- Fred Foo

---

据我所知，gcc优化了自尾递归，但不一定优化其他函数的尾递归。就我所见，当堆栈帧大小不同时，它并不会尝试进行优化。 - tmyklebu

Answer 2

尾递归是可以的，并且是一种很有用的编码技巧。 它不是“坏”的，但是有一些注意事项：

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

2. 一些程序员对递归感到反感，并且知道尾递归始终可以转换为循环，因此认为它总是应该这样做。

出于上述原因，您应该学习如何在尾递归和循环之间进行转换，这将有助于您知道编译器是否可以优化递归。

- Marcin