是否可以使用迭代器实现递归算法？

http://www.seqan.de/dddoc/html/streePreorder.png http://www.seqan.de/dddoc/html/streePreorder.png

我可以存取权限的每个节点的下一个操作。

// postorder dfs 
Iterator< Index<String<char> >, BottomUp<> >::Type myIterator(myIndex); 
for (; !atEnd(myIterator); goNext(myIterator)) 
    // do something with myIterator

但我想在树上使用递归算法。
有没有办法让递归算法（排除每个节点上最大的子树）迭代？
或我如何非递归地访问元素？

编辑：企业的实际问题：
我已经给了递归算法，即在树上的作品。（递归）
我也使用库，我只能用迭代器访问项目（非标准，迭代）

递归< - >迭代。
我该如何解决这个问题？

来源

2009-07-29 n00ki3

你想做一个递归算法，或者你想使它不递归？这是什么？ – jkeys 2009-07-29 16:45:53

他希望递归，但支持迭代器 – Hardryv 2009-07-29 16:56:02

您可以运行递归算法来生成集合，然后遍历集合。有很多理由不这样做，但对于情景而言，与其他成本相比，额外成本将较小。 – Brian 2009-07-29 16:58:54

如果你的迭代器只支持向前遍历（可能是向后），但不遵循树上的链接或快速随机访问，你将很难适应树算法。然而，最终，任何答案都将取决于您的自定义迭代器提供的界面，而这些界面并未提供。

例如，考虑树搜索的简单算法。如果迭代器提供的唯一操作是“从第一个元素开始并逐个移动”，那么显然无法高效地执行树搜索。你也不能实现二分查找。因此，您必须准确提供支持哪些操作的列表，以及（关键）每种操作的复杂性。

来源

2009-07-29 16:58:58 bdonlan

任何递归函数都可以用堆栈实现。如果这是你问的问题。

这是关于这个问题的article by Phil Haack。

性能收益是一种或另一种是推测性的，编译器会在我们后面的代码中执行一些无法预测的代码。实现两个并获得一些实数。如果他们是相似的使用你发现更可读的。

来源

2009-07-29 16:53:04

你可以将的递归函数转换为迭代函数的帮助。

//breadth first traversal pseudo-code 
push root to a stack 
while(stack isn't empty) 
    pop element off stack 
    push children 
    perform action on current node

取决于您想要遍历节点的方式，实现将有所不同。所有递归函数都可以转换为迭代函数。关于如何要求关于具体问题的信息的一般用法。使用堆栈/队列并转换为for循环是应该解决大多数情况的常用方法。

您还应该考虑尾递归以及如何识别它们，因为这些问题可以很好地转化为for循环，许多编译器甚至为您执行此操作。

一些更具数学导向的递归调用可以通过recurrence relations来解决。你遇到这些尚未解决的可能性不太可能，但它可能会让你感兴趣。

//编辑，性能？真的取决于你的实现和树的大小。如果在递归调用中存在很多深度，那么您将得到堆栈溢出，而迭代版本将执行正常。我会更好地掌握递归（如何使用内存），并且您应该能够决定哪种方法更适合您的情况。 Here is an example of this type of analysis with the fibonacci numbers。

来源

2009-07-29 16:53:48 nlucaroni

即使使用递归迭代，您最终还是会得到每个节点的节点访问权限。我需要知道的是：我的迭代器如何被告知先深入，然后：我将如何被通知一个级别已经开始/结束（即递归步骤的开始/结束）。

该知识可以映射到递归算法。

来源

2009-07-29 17:49:37 xtofl

是否可以使用迭代器实现递归算法？

回答

相关问题