logo标签列表

递归与循环的比较

recursioniterationconcept
13
我正在尝试按照这里提供的二叉树示例进行工作：http://cslibrary.stanford.edu/110/BinaryTrees.html。这些示例都通过递归解决问题，我想知道我们是否可以为它们提供迭代解决方案，也就是说，我们是否总是能够确定可以通过递归解决的问题也有迭代解决方案。如果不行，我们可以举什么样的例子来说明只能通过递归/迭代解决的问题？
6个回答
17

在计算机上迭代和递归之间唯一的区别是你使用内置的栈或用户定义的栈，因此它们是等效的。

这是一个有趣（而且我相信是正确的）表达方式。+1 - Josh K
7
除非内置的堆栈溢出，否则迭代版本将正常工作，而递归版本会崩溃。 - mmr
3
@mmr: 在多组件环境中，改变用户定义堆栈的大小比改变内置线程堆栈更容易（因为你的堆栈大小更改可能会干扰其他组件）。递归通常在堆栈上存储更多数据（返回地址和本地状态）。但总体而言，在堆栈使用方面，它们都是相同的。没有回溯的算法可以用迭代方式编码，不需要堆栈，或者使用尾递归，两者的复杂度都是O(1)。有回溯的情况下，两者的大O复杂度也是相同的。 - Ben Voigt
1
那只是理论。现在尝试递归地遍历1024x1024x512体积数据中的每个元素，看看你的堆栈会不会爆炸。 - mmr
1
维护回溯所需的状态量控制着堆栈使用。没有回溯？尾递归->没有堆栈增长。有很多状态？迭代情况也需要千兆字节的内存。 - Ben Voigt
2

根据我的经验，大部分递归解法都可以用迭代的方式来解决。

这也是一种不错的技巧，因为递归解法可能会占用过多的内存和CPU资源。

理论上，所有递归解决方案都可以被重写为迭代算法。但在实践中，你最终会为其中许多解决方案创建和维护一个堆栈框架。 - Chris Lutz
我们能够始终确定吗？我正在尝试寻找更正式的证明，但迄今为止没有成功...了解何时应该努力寻找解决方案，以及何时不需要这样做将非常有帮助... - sachin
1
@sachin: 你可以确定，因为所有递归都是迭代，只是涉及维护状态信息（即栈）的开销。 - Adam Robinson
1

由于递归使用隐式堆栈来存储有关每个调用的信息，因此您始终可以自己实现该堆栈并避免递归调用。因此，是的，每个递归解决方案都可以转换为迭代解决方案。

阅读这个问题以获取证明。

1

递归和迭代是两个工具，在非常基本的层面上做相同的事情：在一组定义好的值上执行重复的操作。它们是可以互换使用的，因为没有一个问题不能通过其中之一来解决。但这并不意味着，一个比另一个更加适合。

0

递归具有在没有已知结束的情况下继续执行的优点。这个优点在调整和线程化的快速排序中体现得淋漓尽致。

虽然你不能生成额外的循环，但是你可以通过递归生成新的线程。

不是这样的。普通的 while 循环可以在没有已知结束条件的情况下继续执行。事实上，快速排序可以用迭代形式编写，其中递归被栈所取代。 - el.pescado - нет войне
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接