问题标签 [recursion]

邮件列表和在线讨论中似乎经常出现的主题之一是攻读计算机科学学位的优点（或缺乏）。对于消极一方来说，似乎一次又一次出现的一个论点是，他们已经编码了几年，而且他们从未使用过递归。

所以问题是：

1. 什么是递归？
2. 我什么时候使用递归？
3. 为什么人们不使用递归？

今天早上，我在阅读Steve Yegge 的《当多态性失败时》时，遇到了一个问题，他的一位同事曾经在潜在员工来亚马逊面试时问他们这个问题。

作为多态性的一个例子，让我们看一下经典的“eval”面试问题，（据我所知）是由 Ron Braunstein 带到亚马逊的。这个问题非常丰富，因为它设法探讨了各种各样的重要技能：OOP 设计、递归、二叉树、多态性和运行时类型、一般编码技能，以及（如果你想让它更难的话）解析理论.

在某些时候，候选人希望意识到您可以将算术表达式表示为二叉树，假设您只使用诸如“+”、“-”、“*”、“/”之类的二元运算符。叶节点都是数字，内部节点都是算子。评估表达式意味着遍历树。如果应聘者没有意识到这一点，你可以温和地引导他们，或者如果有必要，直接告诉他们。

即使你告诉他们，这仍然是一个有趣的问题。

问题的前半部分，有些人（我将保护他们的名字直到我垂死的呼吸，但他们的名字首字母是威利刘易斯）觉得如果你想称自己为开发人员并在亚马逊工作，这是一个工作要求，实际上有点难. 问题是：如何从诸如“2 + (2)”之类的算术表达式（例如在字符串中）到表达式树。在某个时候，我们可能会在这个问题上遇到 ADJ 挑战。

后半部分是：假设这是一个 2 人项目，你的搭档，我们称之为“Willie”，负责将字符串表达式转换为树。你得到了简单的部分：你需要决定 Willie 用什么类来构造树。你可以用任何一种语言来做，但一定要选择一种，否则威利会把汇编语言交给你。如果他感到不耐烦，那将是针对不再生产的处理器。

你会惊讶于有多少候选人喜欢这个。

我不会给出答案，但标准错误解决方案涉及使用 switch 或 case 语句（或只是好的老式级联 ifs）。稍微好一点的解决方案涉及使用函数指针表，而可能最好的解决方案涉及使用多态性。我鼓励你在某个时候完成它。好玩的东西！

所以，让我们尝试通过三种方式来解决这个问题。如何使用级联-if、函数指针表和/或多态性从算术表达式（例如在字符串中）如“2 + (2)”到表达式树？

随意解决一个，两个或所有三个。

[更新：修改标题以更好地匹配大多数答案。]

例如，查看计算第 n 个斐波那契数的代码：

这段代码的问题是它会为任何大于 15 的数字生成堆栈溢出错误（在大多数计算机中）。

假设我们正在计算 fib(10)。在这个过程中，假设 fib(5) 被计算了很多次。有没有办法将它存储在内存中以便快速检索，从而提高递归速度？

我正在寻找一种可以用于几乎所有问题的通用技术。

有没有办法找到特定类型的文件数，而不必遍历 Directory.GetFiles() 或类似方法的所有结果？我正在寻找这样的东西：

我知道我可以创建一个递归函数来调用 Directory.GetFiles ，但是如果我可以在不进行所有迭代的情况下做到这一点，那将会更加简洁。

编辑：如果不递归和迭代自己就不可能做到这一点，那么最好的方法是什么？

在开始学习 lisp 时，我遇到了tail-recursive一词。究竟是什么意思？

我有一个递归算法，它逐个字符地遍历字符串，并对其进行解析以创建树状结构。我希望能够跟踪解析器当前所在的字符索引（对于错误消息以及其他任何内容），但我并不热衷于实现像元组这样的东西来处理多个返回的类型。

我尝试使用 Integer 类型，在方法外部声明并传递给递归方法，但因为它是最终的，递归调用增量在我返回时被“遗忘”。（因为Integer值的递增使得传值对象引用指向一个新对象）

有没有办法获得类似于不会污染我的代码的工作？

在下面的代码中，我在 SQL Server 2005 中使用递归 CTE（公用表表达式）来尝试查找基本层次结构的顶级父级。此层次结构的规则是每个 CustID 都有一个 ParentID，如果 CustID 没有父级，则 ParentID = CustID 并且它是最高级别。

所以如果 tblCustomer 看起来像这样：

我从上面的代码得到的结果是：

我想要的只是该结果的最后一行：

如何只返回 CTE 中生成的最后一条记录（最高级别的 CustID）？

另请注意，此表中有多个不相关的 CustID 层次结构，因此我不能只执行 SELECT * FROM tblCustomer WHERE ParentID = CustID。我无法按 ParentID 或 CustID 排序，因为 ID 号与其在层次结构中的位置无关。

在编写生产质量的 VC++ 代码时，是否可以使用递归？为什么或者为什么不？

Is there a fast and clean way of returning a JSON hash back from any node in a Ruby on Rails' acts_as_nested_set without using recursion?

Here's the recursive solution for reference:

我有一个以下格式的 XML 文件：

谁能给我一些关于如何使用 C# 遍历文件的指导？