logo标签列表

递归还是迭代？

language-agnosticoptimizationrecursioniteration
30

我喜欢递归。我认为它可以简化很多东西。也许有人不同意；但我认为它还使得代码更易于阅读。然而，我注意到在像C#这样的语言中递归并没有像在LISP中那样经常使用（顺便说一下，LISP是我的最爱，因为它支持递归）。

是否有人知道是否有任何好理由不在像C#这样的语言中使用递归呢？ 是否比迭代更昂贵？

2
递归在LISP中被广泛使用，因为你没有其他选择。 - Adrian Zanescu
3
在现代的Lisp系统中，有许多其他选项。你的陈述在四十年前可能是正确的。 - David Thornley
精确重复：https://dev59.com/JXVD5IYBdhLWcg3wJIEK 但这个问题太老了，不值得再编辑一次让它重新浮现在主页。 - Bill the Lizard
1
@David 对于Scheme仍然是正确的，而且OP从未指定CLISP或Scheme，所以... - new123456
我并不认为递归更易读。对我来说，循环要简单得多。尽管如此，我仍然更喜欢递归，因为它看起来更正确、更干净。 - nawfal
一个好的比较可以在这里找到：https://www.geeksforgeeks.org/difference-between-recursion-and-iteration/ - Asif
14个回答
18

它们比迭代更昂贵吗？

是的，它们比迭代更昂贵。许多Lisp变体支持尾调用优化的概念，它允许将许多递归函数调用转换为迭代函数调用（这有点简化了）。如果不支持尾调用，则递归函数调用会在堆栈上使用越来越多的内存。

许多Lisp不支持尾调用。 - Jules
1
@julesjacobs 你可能是对的，我写的那个肯定没有；然而，值得注意的是Scheme 需要它。 - Aaron Maenpaa
任何好的编译器都应该优化掉尾调用，可惜很多编译器不够优秀。 - Greg
一种函数式语言可能具有使其几乎不可能进行尾调用优化的特性。在JavaScript的情况下，这些特性被认为“不值得”，但在这些特性最终被删除之前可能需要数年时间。 - Erik Reppen
16

它们比迭代更昂贵吗？

是的。递归需要创建一个新的堆栈帧以及一个调用和返回，而迭代通常只需要一个比较和分支，使其速度明显更快。但是，编译器可以对某些递归调用（即尾递归）执行尾调用优化，从而使它们重用堆栈帧，大大降低了递归调用的成本，有效地将其转换为迭代。Scheme 实际上要求 Scheme 编译器实现尾调用优化。

11

像Lisp和F#这样的函数式编程语言可以将许多尾递归函数作为循环内部实现，从而能够避免函数调用时的堆栈开销。C#不支持尾递归，但是F＃支持。

2
C＃并未规定它，但底层CLR包括尾调用指令，因此这是一种合理的优化。注意：从.NET 2.0开始，尾调用比常规调用慢。 - plinth
11
现代CPU的编译器和架构可以对循环进行许多优化，但递归则无法做到。例如，处理器能够进行乐观计算。当处理器找到一个迭代空间时，它知道需要多长时间才能完成。从一开始，下一次循环启动之前就没有必要每次都进行检查。因此，它们对操作进行流水线处理。由于大多数CPU可以同时执行多个操作（通过流水线处理），所以你可以在比递归更短的时间内解决迭代空间。即使进行了尾递归优化，因为CPU事实上正在同时处理大约4个循环（可以获得4倍的性能提升）。这种提升将取决于CPU的架构。架构可能是提高性能的重要因素，下一代CPU可能会进一步推动性能提升。
递归的真正问题在于我们的硬件是基于VonNeumann的（可实现变体的图灵机），而不是Lisp机器，虽然有一些专用的Lisp硬件，但你不会在任何桌面电脑上找到它 :)
6
我们需要一个奖项来表彰在 Stack Overflow 中发布的最长句子。 ;) - Michael Myers
2
最长的可理解句子，至少是这样。 - too much php
确实易懂，我甚至没有注意到这个长句子，直到mmyers指出来，但我经常犯这种错误，所以我对它免疫了。明白吗？ - Karl
2
我显然是一个文学怪人，完全展开了那个句子，哇。 - Robert Gould
8
使用递归有许多优缺点。无疑，代码的简洁性是最大的优点，这也有助于更好地维护代码并减少错误。
递归最大的危险在于边缘情况，即算法失控以打破函数堆栈限制。一些语言，例如Progress的ABL语言，具有允许嵌套调用的最高级别参数。这些通常很低，添加递归可能会导致应用程序突破该限制。
简而言之，递归应始终使用紧密的终止条件进行实现，否则调试可能非常困难（由于不可预测性）并且可能会在生产代码中引起严重问题。
对于内存和速度的考虑，除非该方法本身很短（时间上），被多次调用，否则性能并不重要。
例如：如果您使用递归扫描硬盘的所有文件和文件夹，则递归所做的性能影响微不足道，因为它需要的时间比击中硬盘并获取文件系统信息的时间长得多。在这种情况下，递归可能比迭代处理更可取。
另一个例子：如果您扫描树结构的节点，则迭代过程可能更有利，因为我们没有涉及函数堆栈，这意味着我们使用的内存更少，可能让硬件使用更多缓存。有关详细信息，请参见Robert Gould的回答。
6

如果一个算法最自然的表达形式是递归形式，并且如果堆栈深度很小（在log(N)范围内，即通常<20），那么请务必使用递归。（任何由于迭代而导致的性能增益将是一个小常数因子）。

如果有任何危险，使得堆栈增长得过大，并且你的语言/编译器/运行时系统不能保证尾调用优化，则应避免使用递归算法。

3

有没有人知道在像C#这样的语言中不使用递归的好理由？它比迭代更昂贵吗？

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

2
选择不仅基于要解决的问题，也基于所使用的语言。在类C语言（如Java、C#等）中，我的第一反应是避免使用递归，因为对我来说它看起来完全陌生（而且我无法进行递归思考），更别提潜在的堆栈滥用问题了。然而，有些问题几乎没有理由使用除递归之外的任何其他方法，比如树遍历问题。迭代解决方案完全可行，但代码会更长、更容易出错，并且几乎肯定会更难读懂。
然而，更动态的语言（如Lisp或Python）通过各种方式使递归更自然。我的个人想法是，无论面对什么问题，首先要寻找一个迭代解决方案，但是结果因人而异。
最后，最好的方法可能就是直接写下来。很有可能你总会把它扔掉。
1
如果一个问题可以被归约为迭代，则我进行迭代。
如果一个问题需要递归（例如树导航），那么我进行递归。
话虽如此，我主要使用C#制作业务应用程序——我相信科学编程有不同的需求。
1

Scheme是我所知道的唯一需要尾调用优化的Lisp方言，而且它们往往会大量使用递归。在其他不需要这个特性的Lisp方言中（比如Common Lisp），我并没有看到递归被使用得比其他语言更多。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接