我正在尝试使用此处给出的树示例：http: //cslibrary.stanford.edu/110/BinaryTrees.html 这些示例都通过递归解决问题，我想知道我们是否可以为每个示例提供迭代解决方案它们，意思是，我们是否可以始终确定可以通过递归解决的问题通常也将具有迭代解决方案。如果不是，我们可以举出什么例子来说明只能通过递归/迭代来解决的问题？
--
问问题
1221 次
6 回答
17
计算机上的迭代和递归之间的唯一区别是您使用的是内置堆栈还是用户定义的堆栈。所以它们是等价的。
于 2010-04-17T20:13:54.417 回答
2
以我的经验，大多数递归解决方案确实可以迭代解决。
这也是一种很好的技术，因为递归解决方案可能在内存和 CPU 消耗方面的开销太大。
于 2010-04-17T20:12:57.490 回答
1
由于递归使用隐式堆栈来存储有关每个调用的信息，因此您始终可以自己实现该堆栈并避免递归调用。所以是的，每个递归解决方案都可以转换为迭代解决方案。
阅读这个问题以获得证明。
于 2010-04-17T20:17:24.517 回答
1
递归和迭代是两种工具，在非常基本的层面上，它们做同样的事情：对一组定义的值执行重复操作。它们是可互换的，因为没有任何问题在某种程度上只能由其中一个来解决。然而，这并不意味着一个不能比另一个更适合。
于 2010-04-17T20:18:16.017 回答
0
递归的优点是它可以在没有已知结束的情况下继续进行。一个完美的例子是经过调整和线程化的快速排序。
你不能产生额外的循环，但你可以通过递归产生新的线程。
于 2010-04-17T20:11:37.197 回答
0
作为一个“老家伙”，我回忆起递归下降解析器更容易编写，但基于堆栈的迭代解析器性能更好。这是一篇似乎用指标支持该想法的文章：
需要注意的一件事是作者提到使用递归下降超出调用堆栈。迭代的、基于堆栈的实现可以更有效地利用资源。
于 2010-04-17T20:40:03.333 回答