30

我喜欢递归。我认为它简化了很多事情。另一个人可能不同意；我认为这也使代码更容易阅读。但是，我注意到递归在 C# 等语言中的使用不像在 LISP 中那样多（顺便说一下，由于递归，这是我最喜欢的语言）。

有谁知道是否有充分的理由不在 C# 等语言中使用递归？它比迭代更昂贵吗？

4

14 回答 14

18

它们比迭代更昂贵吗？

对，他们是。许多 Lisp 变体支持“尾调用优化”的想法，它允许将递归函数调用的许多用途转换为迭代函数调用（这有点简化）。如果不支持尾调用，则递归函数调用将逐渐使用堆栈上的更多内存。

于 2009-01-26T00:11:40.003 回答
16

它们比迭代更昂贵吗？

对，他们是。递归需要在调用和返回的同时创建一个新的堆栈帧，而迭代通常只需要比较和分支，从而大大加快速度；但是，编译器可以对某些递归调用（即尾调用）执行尾调用优化，这允许它们重用堆栈帧，从而大大降低递归调用的成本并有效地将它们转化为迭代。Scheme 实际上要求方案编译器实现尾调用优化。

于 2009-01-26T00:13:10.983 回答
11

Lisp 和 F# 等函数式语言可以在内部将许多尾递归函数实现为循环，并且能够避免函数调用的堆栈开销。C# 不支持尾递归，但 F# 支持。

于 2009-01-26T00:12:49.893 回答
11

现代 CPU 的编译器和架构可以通过迭代进行很多优化，而递归则无法做到。例如，处理器进行乐观计算的能力。当处理器找到一个迭代空间时，它知道需要多长时间。从一开始，在开始下一个循环之前，并没有真正需要每次检查。因此，他们将操作流水线化。由于大多数 CPU 可以同时执行多个操作（通过流水线），因此您可以在比递归更短的时间内解决迭代空间问题。即使是尾部优化也是如此，因为 CPU 实际上一次处理大约 4 个循环（以获得 x4 的性能增益）。这种增益将取决于 CPU 的架构。该架构可能是收益的重要组成部分，下一代 CPU 会进一步推动收益。

递归的真正问题是我们的硬件是基于冯诺依曼的（图灵机的可实现变体），而不是 Lisp 机器，虽然有一些专门的 Lisp 硬件，但你不会找到任何带有它的桌面 :)

于 2009-01-26T01:26:25.017 回答
8

使用递归有很多优点和缺点。毫无疑问，代码的简单性是最大的优点，它也有助于更好的代码可维护性和更少的错误。

递归的最大危险是边缘情况，即算法失控以打破函数堆栈限制。某些语言（其中之一是 Progress 的 ABL 语言）具有允许的最高级别嵌套调用的参数。这些通常很低，并且在混合中添加递归可能会使应用程序突破该限制。

简而言之，递归应该始终在紧密终止情况下实现，否则它可能非常难以调试（因为不可预测性）并且可能导致生产代码中的严重问题。

对于内存和速度的问题，除非这是一个方法本身很短（时间明智）被多次调用，否则性能如何并不重要。

示例：如果您使用递归扫描硬盘驱动器的所有文件和文件夹，那么递归对性能的影响与访问硬盘驱动器并获取文件系统信息所需的时间相比是微不足道的。在这种情况下，递归可能比迭代处理更受欢迎。

另一个例子：如果您扫描树结构的节点，迭代过程可能更有益，因为我们没有过多地涉及函数堆栈，这意味着我们使用的内存更少，并且可能让硬件使用更多的缓存。有关详细信息，请参阅 Robert Gould 的回复。

于 2009-01-26T06:26:15.800 回答
6

如果一个算法可以最自然地以递归形式表示，并且如果堆栈深度很小（在 log(N) 范围内，即通常 <20），那么无论如何都要使用递归。（由于迭代而产生的任何性能增益都将是一个很小的常数因素）。

如果存在堆栈变大的危险，并且如果您的语言/编译器/运行时系统不能保证尾调用优化，则应避免使用递归算法。

于 2009-01-26T14:19:24.567 回答
3

有谁知道是否有充分的理由不在 C# 等语言中使用递归？它比迭代更昂贵吗？

是的，因为 C# 不支持尾递归。当使用递归对大型集合进行简单迭代时，如果递归太深，很容易得到 StackOverflowException 并导致应用程序崩溃。

于 2009-01-26T23:02:12.390 回答
2

The choice isn't based solely on the problem to be solved, but also on the language used. In C-style languages (Java, C#, or what have you) my knee-jerk response is to avoid recursion, as it looks completely alien to me (and I just can't think recursively), to say nothing of the potential for stack abuse. However, there are some problems for which it makes almost no sense to use anything other than recursion - tree traversal being a good example. An iterative solution is completely plausible, but the code would be bigger, buggier, and almost certainly less readable.

However, more dynamic language (such as Lisp or Python) go to great lengths to make recursion a more natural possibility. My personal response is to look for an iterative solution first, no matter what the problem, but varying mileage makes a horse race.

In the end, the best bet is probably to just write it. Chances are good that you'll throw it out once in any case.

于 2009-01-26T21:14:41.873 回答
1

Scheme is the only Lisp dialect I know of that requires tail-call optimization, and they tend to use recursion a lot. In other Lisp dialects that don't require this (like Common Lisp), I don't see recursion used any more than in any other language.

于 2009-01-26T21:15:41.373 回答
1

递归比迭代（不可能/更难）并行化

现代 CPU 具有多核，因此如果您设计用于递归，则使用parallel.for（以及此类技术）进行直接优化会变得更加困难。

然而，并行化仍然相当模糊，使用它的人相对较少。

此外，我认为递归算法更容易设计和思考，因为它们同时涉及的代码和变量略少。当没有性能需要时，我通常会使用递归。

于 2009-01-26T23:19:34.773 回答
1

如果一个问题可以简化为一个迭代，那么我就迭代。

如果问题需要递归（例如树导航），那么我会递归。

话虽如此，我主要使用 C# 制作业务线应用程序 - 我确信科学编程有不同的要求。

于 2009-01-26T20:42:59.020 回答
0

我认为递归函数必须放在堆栈上 - 每次函数调用自身时，该函数的另一个副本都会进入函数堆栈，依此类推。问题是，在某些时候，堆栈用完了存储函数的空间，所以如果数字变大，递归解决方案可能不起作用。我知道是因为它咬了我的屁股——我对free()我的整个链表有一个很棒的递归函数，然后我用我可以制作的最大链表对它进行了测试，但出现了一个错误（我相信这是一个段错误——绝对应该是堆栈溢出:)）。

迭代函数没有这些错误——在机器语言中，它们表示为简单的 'jmp' 或 'je' 等，因此它们永远不会耗尽函数堆栈上的空间，并且实际上更干净。

这是一个完全主观的问题，但如果不是因为递归在您的计算机中内置了限制，我会说这是一个更好的解决方案。一些问题的迭代解决方案看起来很丑，而递归解决方案看起来更干净更好。但这就是生活。

于 2009-01-26T00:16:33.677 回答
0

我只想说，在 XSLT 中，变量在创建后是只读的。因此，可以使用索引 for 循环完成的事情，例如

for(int i=0; i < 3; i++) doIt(i);

实际上是通过递归完成的。相当于

public rediculous(i) {
    doIt(i);
    if (i < 3) rediculous(i + 1);
}

我实际上会在这里提供一个 XSLT 示例，但是所有这些输入都会让 Baby Jesus 哭泣。

于 2009-01-26T23:17:55.680 回答
0

在处理诸如列表或向量之类的固有线性数据结构时，更喜欢迭代构造而不是递归的一个原因是它更好地传达了代码的意图。当迭代足够时不加选择地使用递归时，读者通常需要更多的努力来辨别程序的结构。

于 2009-01-26T14:08:30.453 回答