“有必要”的命令式语言递归的使用(“Necessary” Uses of Recursion in

我最近看到一对夫妇一起的，该行不同的地方的意见：“我从学校里了解到递归，但从来没有使用过或认为有必要对自那以后。” （递归似乎是“书本知识”当中某一群程序员的通俗的例子。）

好了，这是真的，在命令式语言如Java和Ruby [1]，我们一般采用迭代和避免递归，部分原因是由于堆栈溢出的风险，部分是因为它在这些语言的样式大部分程序员用来。

现在我知道了，严格来说，也有这样的语言递归没有“必要”用途：人们总是可以某种方式与迭代替换递归，不管事情变得多么复杂。所谓“必要”在这里，我说的是以下几点：

你能想到的在这样的语言代码中的任何具体的例子，其中递归是如此明显优于迭代（为清晰，效率，或以其他方式原因），您使用递归无论如何，并且转化为迭代会是一个很大的损失？

递归遍历树已经在答复中多次提到：什么是它究竟是你的特定用途的它是由递归比使用库定义的迭代器更好，如果它可用？

[1]：是的，我知道，这些也都是面向对象的语言。这不是对这个问题直接相关的，但是。

Answer 1:

有递归没有“必要”的用途。所有的递归算法可以转换为迭代的。我似乎记得一个堆叠在必要的，但我不记得确切的建设从我的头顶。

实事求是地讲，如果你不使用递归以下（即使是在命令式语言）你有点生气：

树遍历
图表
乐星/解析
排序

Answer 2:

当你走任何一种树状结构，例如

使用递归下降解析器解析语法
走DOM树（如解析HTML或XML）

还，调用对象成员的的toString（）每toString（）方法可以被认为是递归的，太。所有对象序列化的算法是递归的。

Answer 3:

在我的工作递归很少用于任何算法。像阶乘等物品都是由简单的循环来解决更可读（和有效）。当它出现，通常是因为你正在处理一些数据，在本质上是递归的。例如，在一个树结构中的节点可被递归地处理。

如果你要编写一个程序来走，例如二叉树的节点，你可以写一个处理节点，称自己来处理每一个它的孩子们的功能。这将是比试图保持所有不同状态，每个子节点，你通过它们循环更有效。

Answer 4:

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

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

Answer 5:

在我看来，递归算法是天作之合当数据结构也是递归的。

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

我不明白为什么我会想写反复。

Answer 6:

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

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

该字符串是这样的：

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

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

Answer 7:

递归总是可以被重写为与外部叠层迭代。但是，如果你确定你没有很深的递归，这将导致风险计算器，递归是一种非常方便的事情。

一个很好的例子是遍历一个已知的操作系统上的目录结构。通常你知道它有多深能（最大路径长度是有限的），因此不会有一个计算器。与外部栈操作的方式从迭代相同不太方便。

Answer 8:

有人说“什么树”。我可能是过于谨慎了，我知道堆栈是时下大，但我还是不会在树典型使用递归。我会，但是，做一个平衡树 。

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

    }

这可以在不使用递归的代码一些额外的线来完成。

文章来源: “Necessary” Uses of Recursion in Imperative Languages