命令式语言中“必要”的递归使用

Question

我最近在不同的地方看到一些评论，大致是：“我在学校学过递归，但自那以后从未使用过或感觉需要使用它。”（在某些程序员群体中，递归似乎是“书本学习”的一个流行示例。）

虽然在Java和Ruby等命令式语言中，我们通常使用迭代并避免使用递归，部分原因是由于堆栈溢出的风险，同时也是因为这是这些语言中大多数程序员习惯的编程风格。

现在我知道，严格来说，在这些语言中没有必要使用递归：无论情况有多复杂，都可以通过某种方式用迭代来代替递归。在此，“必要”意味着以下内容：

您能否想到任何特定的代码示例，在这些语言中递归比迭代更好（出于清晰、效率或其他原因），以至于您仍然使用递归，并转换为迭代将会有很大的损失？

答案中已经多次提到过递归遍历树：对于您特定的使用场景，递归与使用库定义的迭代器相比有何优势？

- cjs

---

帖子正文“递归比迭代更好”的说法表明您知道标题存在问题：没有必要使用递归。 - AakashM

确实，这个标题并不完美：我刚刚更新了问题，以表明我理解了这一点。我花了很多时间思考，但找不到更好的词来恰当地捕捉问题的精神。欢迎提出建议。 - cjs

递归会导致人们进入堆栈溢出（Stack Overflow）的情况。 - ilya n.

当然是stackoverflow.com！ - ilya n.

你特定使用递归算法，相较于使用预定义的迭代器库，有哪些优势？我打赌大部分情况下，基础迭代器的实现很可能也是用递归来提供可迭代接口的。 - Russell Leggett

Answer 1

递归没有"必要"的用法。所有递归算法都可以转换为迭代算法。我记得需要使用栈，但我现在想不起来确切的结构。

实际上，如果您没有在以下情况下（即使在命令式语言中）使用递归，那么您有点疯狂：

1. 树遍历
2. 图形
3. 词法分析/语法分析
4. 排序

- Kevin Montrose

---

请参阅帖子及其评论以了解有关“必要”一词的讨论。 - cjs

答案符合当时提出的问题。 - Kevin Montrose

只有当你故意将“必要”这个词的含义与我原本的意图不同解释时，才会出现问题。请在这种情况下将“必要”解释为“从实际角度考虑，如果你想避免被认为是有点疯狂的话是必要的”。在这种情况下，你的回答是矛盾的。 - cjs

真是太神奇了，你的建议几乎完全引用了答案原文的内容。 - Kevin Montrose

我实际上使用显式堆栈进行解析迭代。这更有意义，因为它将括号匹配抽象到一个单独的层，并且我不必来回扫描以找到需要递归解析的部分。 - Challenger5

Answer 2

当你遍历任何类型的树形结构时，例如

• 使用递归下降解析器分析语法
• 遍历DOM树（例如解析后的HTML或XML）

此外，调用对象成员的toString()方法的每个toString()方法也可以被视为递归。所有对象序列化算法都是递归的。

- mfx

---

toString()方法不是递归的，序列化也不总是递归的。一个例外可能是列表中包含列表，或者字典中包含字典，但通常情况下它们不是递归的。 - G B

好的一般性观点，但我个人不会在DOM树上进行递归。我不知道，也许我对“永远不要相信客户端的数据”太保守了。 - ilya n.

除非结构本身是递归的，否则它们是不同的toString()和serialize()方法。递归涉及调用相同的函数，而不是具有相同名称的函数。 - Robert Fraser

可以将每个toString()实现都视为属于“同一个”函数，因为它们都覆盖了Object.toString()。在非面向对象语言中，toString()可以被实现为toString(Object)，并带有巨大的基于类型的分派，这无疑会被认为是递归的。 - mfx

Answer 3

在我的工作中，递归很少用于任何算法。像阶乘等问题通常使用简单的循环更易于理解（并且更有效）。当它出现时，通常是因为您正在处理某些具有递归性质的数据。例如，可以递归处理树结构上的节点。

如果您要编写一个程序来遍历二叉树的节点，您可以编写一个处理一个节点的函数，并调用自己来处理每个子节点。这比尝试维护每个子节点的所有不同状态要更有效，而您循环遍历它们。

- Simon P Stevens

Answer 4

最著名的例子可能是由C.A.R. Hoare开发的快速排序算法。

另一个例子是遍历目录树以查找文件。

- Jochen Walter

---

支持目录遍历。这是一个非常常见的任务，在使用递归之前会很麻烦。 - erikkallen

Answer 5

在我看来，当数据结构本身也是递归的时候，递归算法非常适合。

def traverse(node, function):
    function(this)
    for each childnode in children:
        traverse(childnode, function)

我不明白为什么要迭代地编写那段代码。

- Kylotan

Answer 6

这全都关于你正在处理的数据。

我编写了一个简单的解析器，将字符串转换为数据结构，这可能是我在 Java 工作 5 年中唯一的例子，但我认为这是正确的方法。

字符串看起来像这样：

"{ index = 1, ID = ['A', 'B', 'C'], data = {" +
   "count = 112, flags = FLAG_1 | FLAG_2 }}"

对于这个问题，最好的抽象是一棵树，其中所有叶节点都是原始数据类型，而分支可以是数组或对象。这是典型的递归问题，虽然非递归解决方案也是可能的，但要复杂得多。

- G B

Answer 7

递归总是可以用外部栈重写成迭代。然而，如果你确定不会有很深的递归风险导致堆栈溢出，那么递归是一件非常方便的事情。

一个很好的例子是在已知操作系统上遍历目录结构。通常你都知道它的深度（最大路径长度有限），因此不会出现堆栈溢出。使用外部栈进行迭代遍历并不是那么方便。

- sharptooth

Answer 8

有人说过“任何树都可以用递归解决”。我可能太谨慎了，虽然现在栈很大，但我仍然不会在典型的树上使用递归。不过，在一个平衡树上我会这样做。

- ilya n.

Answer 9

我有一个报告列表。我在包含此列表的类上使用索引器。使用索引器按其屏幕名称检索报告。如果该屏幕名称的报告不存在，则在索引器中加载报告并递归调用自身。

public class ReportDictionary
    {
        private static List<Report> _reportList = null;

        public ReportColumnList this[string screenName]
        {
            get
            {
                Report rc = _reportList.Find(delegate(Report obj) { return obj.ReportName == screenName; });

                if (rc == null)
                {
                    this.Load(screenName);
                    return this[screenName]; // Recursive call
                }
                else
                    return rc.ReportColumnList.Copy();
            }
            private set
            {
                this.Add(screenName, value);
            }
        }

    }

可以使用一些额外的代码行来完成，而无需使用递归。

- Rashmi Pandit