递归与循环
我正在尝试使用此处给出的树示例进行工作： http://cslibrary.stanford.edu /110/BinaryTrees.html 这些例子都是通过递归来解决问题的，我想知道我们是否可以为每个例子提供一个迭代解决方案，也就是说，我们能否始终确保一个可以通过递归解决的问题通常也有一个迭代解决方案。如果不是，我们可以举什么例子来说明只能通过递归/迭代解决的问题？
--
I am trying to do work with examples on Trees as given here: http://cslibrary.stanford.edu/110/BinaryTrees.html
These examples all solve problems via recursion, I wonder if we can provide a iterative solution for each one of them, meaning, can we always be sure that a problem which can be solved by recursion will also have a iterative solution, in general. If not, what example can we give to show a problem which can be solved only by recursion/Iteration?
--
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
由于递归使用隐式堆栈来存储有关每个调用的信息，因此您始终可以自己实现该堆栈并避免递归调用。所以是的，每个递归解决方案都可以转换为迭代解决方案。
阅读这个问题以获得证明。
Since recursion uses an implicit stack on which it stores information about each call, you can always implement that stack yourself and avoid the recursive calls. So yes, every recursive solution can be transformed into an iterative one.
Read this question for a proof.
递归和迭代是两种工具，从根本上讲，它们执行相同的操作：对一组定义的值执行重复操作。它们是可以互换的，因为在某种程度上，没有任何问题不能仅通过其中之一来解决。然而，这并不意味着其中一个不能比另一个更适合。
Recursion and iteration are two tools that, at a very fundamental level, do the same thing: execute a repeated operation over a defined set of values. They are interchangeable in that there is no problem that cannot, in some way, be solved by only one of them. That does not mean, however, that one cannot be more suited than the other.
递归的优点是它可以在没有已知结束的情况下继续进行。一个完美的例子是调整和线程快速排序。
您无法生成额外的循环，但可以通过递归生成新线程。
Recursion has the advantage where it will continue without a known end. A perfect example of this is a tuned and threaded Quick Sort.
You can't spawn additional loops, but you can spawn new threads via recursion.
作为一个“老家伙”，我回忆起递归下降解析器更容易编写，但基于堆栈的迭代解析器性能更好。这里有一篇文章似乎通过指标支持了这个想法：
http://www.texttoolkit.com/index.php?option=com_content&view=article&catid=35%3Atechnology&id=60%3Abeyond- recursive-descent&Itemid=55
需要注意的一件事是作者提到了递归下降会导致调用堆栈溢出。基于堆栈的迭代实现可以更加有效地利用资源。
As an "old guy," I fall back to my memory of learning that recursive descent parsers are easier to write, but that stack-based, iterative parsers perform better. Here's an article that seems to support that idea with metrics:
http://www.texttoolkit.com/index.php?option=com_content&view=article&catid=35%3Atechnology&id=60%3Abeyond-recursive-descent&Itemid=55
One thing to note is the author's mention of overrunning the call stack with recursive descent. An iterative, stack-based implementation can be much more efficient of resources.
计算机上的迭代和递归之间的唯一区别在于您使用内置堆栈还是用户定义的堆栈。所以它们是等价的。
The only difference between iteration and recursion on a computer is whether you use the built-in stack or a user-defined stack. So they are equivalent.
根据我的经验，大多数递归解决方案确实可以迭代解决。
这也是一项很好的技术，因为递归解决方案可能会在内存和 CPU 消耗方面产生太大的开销。
In my experience, most recursive solution can indeed be solved iteratively.
It is also a good technique to have, as recursive solutions may have too large an overhead in memory and CPU consumptions.