为什么尾递归是递归的坏用法？

Question

我最近在学习日期结构。在Mark的书“C中的数据结构和算法分析”中，为什么他说尾递归是递归的糟糕用法，最好不要在第三章中使用它？但我看到很多人说它在网上很有用。

Answer 1

不一定是坏的。尾递归总是等价于循环，根据编译器的不同，显式编写循环可能更有效。(*)现代编译器GCC等现代编译器可以优化尾递归，但他们并不总是能识别它。当他们看不到它时，递归将占用堆栈空间。

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

当一个算法只有一个递归(也就是尾递归)时，最好立即将它写成一个循环，因为递归函数可能比循环更难调试。

(*)我想我们只是在谈论C。在其他一些语言中，尾递归可以被认为是循环(函数式语言)的自然方式，也可以被看作是一种彻底的厌恶(Python)。

Answer 2

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

1. 与任何递归一样，除非您的编译器能够优化它(请选中此)，否则它将消耗堆栈帧。对于较大的输入，这可能导致堆栈溢出。
2. 有些程序员对递归有孩子气的反感，并且知道尾递归总是可以转换成循环，所以相信应该总是这样。

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