我给了这样一棵树:
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
但我想在树上使用递归算法。
有没有一种方法可以使递归算法(排除每个节点上最大的子树)迭代？
或者我如何非递归地访问元素？
编辑:
实际问题:
我已经给出了一个适用于树的递归算法。 (递归)
我还使用了一个库，在该库中我只能使用迭代器(非标准，迭代)访问项目
递归 <-> 迭代。
我该如何解决这个问题？
最佳答案
您可以借助堆栈将那个递归函数转换为迭代函数。
//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 .
关于c++ - 是否可以使用迭代器实现递归算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1201560/