递归还是迭代？

Question

递归还是迭代？

language-agnosticoptimizationrecursioniteration

30

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

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

- Ten P.

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个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric · Answer 1

递归比迭代更难并行化（或者说几乎不可能）。

现代CPU有多核心，因此如果你设计的是递归算法，直接使用parallel.for（以及类似的技术）进行优化会变得更加困难。

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

此外，我认为递归算法更容易设计和思考，因为它们涉及的代码和变量稍微少一些。如果没有性能需求，我通常会选择递归。

- Chris Lutz · Answer 2

我认为递归函数必须放在一个栈上 - 每次函数调用自身时，另一个该函数的副本就会进入函数栈，以此类推。问题在于，在某个点上，栈会耗尽存储函数的空间，因此如果数字变得太大，递归解决方案可能无法工作。我知道这是因为它曾经让我吃过亏 - 我有一个很棒的递归函数来free()我的整个链表，然后我用最大的链表进行了测试，结果出现了错误（我相信这是一个段错误 - 明显应该是堆栈溢出 :)）。

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

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

- huaiyuan · Answer 3

当处理类似于列表或向量这样的固有线性数据结构时，选择迭代构造而不是递归的原因之一是它更好地传达了代码的意图。当递归被滥用而迭代足以胜任时，往往需要更多的努力才能让读者理解程序的结构。

- nsayer · Answer 4

我想提醒大家，在XSLT中，一旦变量被创建后就是只读的。因此，像使用索引for循环做的事情，

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

实际上是使用递归完成的。类似于

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

我本来想在这里提供一个XSLT示例，但是所有的打字让耶稣宝宝哭了。