14

我最近在几个不同的地方看到类似这样的评论：“我在学校学习了递归，但从那时起就再也没有使用过或觉得有必要使用它。” （递归似乎是特定程序员群体中“书本学习”的一个流行例子。）

的确，在 Java 和 Ruby[1] 等命令式语言中，我们通常使用迭代并避免递归，部分原因是存在堆栈溢出的风险，部分原因是大多数程序员在这些语言中习惯于使用这种风格.

现在我知道，严格来说，在这些语言中没有“必要”使用递归：无论事情变得多么复杂，人们总是可以以某种方式用迭代代替递归。这里的“必要”是指以下内容：

你能想到在这样的语言中递归比迭代好得多的任何特定代码示例（出于清晰、效率或其他原因），你无论如何都使用递归，而转换为迭代将是一个很大的损失？

答案中多次提到递归行走树：您对它的特定使用究竟是什么使递归比使用库定义的迭代器更好，它是否可用？

[1]：是的，我知道这些也是面向对象的语言。然而，这与这个问题没有直接关系。

4

9 回答 9

12

递归没有“必要的”用途。所有递归算法都可以转换为迭代算法。我似乎记得有一个堆栈是必要的，但我不记得我头顶上的确切结构。

实际上，如果您没有对以下内容使用递归（即使在命令式语言中），您有点生气：

  1. 树遍历
  2. 图表
  3. 词法分析/解析
  4. 排序
于 2009-06-18T09:22:38.257 回答
8

例如，当您行走在任何一种树状结构时

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

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

于 2009-06-18T09:04:04.067 回答
7

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

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

于 2009-06-18T08:28:54.200 回答
6

最著名的例子可能是 CAR Hoare 开发的快速排序算法。

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

于 2009-06-18T09:15:21.297 回答
4

在我看来，当数据结构也是递归的时候，递归算法是很自然的选择。

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

我不明白为什么我想迭代地写那个。

于 2009-06-18T09:37:42.517 回答
1

这一切都与您正在处理的数据有关。

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

字符串看起来像这样：

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

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

于 2009-06-18T08:57:17.620 回答
1

递归总是可以用外部堆栈重写为迭代。但是，如果您确定不会冒会导致 stackoverflow 的非常深的递归的风险，那么递归是一件非常方便的事情。

一个很好的例子是遍历已知操作系统上的目录结构。您通常知道它可以有多深（最大路径长度是有限的），因此不会有 stackoverflow。通过使用外部堆栈进行迭代来做同样的事情并不是那么方便。

于 2009-06-18T09:26:21.947 回答
1

有人说“任何树”。我可能过于谨慎，而且我知道现在堆栈很大，但我仍然不会在典型的树上使用递归。但是，我会在平衡树上进行。

于 2009-06-19T22:58:39.217 回答
0

我有一份报告清单。我在包含此列表的班级上使用索引器。使用索引器通过它们的屏幕名称检索报告。在索引器中，如果该屏幕名称的报告不存在，它会加载报告并递归调用自身。

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);
            }
        }

    }

这可以在不使用一些额外代码行的递归的情况下完成。

于 2009-06-18T08:44:30.500 回答