问有可能用迭代器实现递归算法吗？

EN

如果您的迭代器只支持前向(也可能是向后)遍历，而不支持树上的链接或快速随机访问，那么您将很难使树算法适应它。但是，最终任何答案都将取决于您尚未提供的自定义迭代器提供的接口。

例如，考虑简单的树搜索算法。如果迭代器给出的唯一操作是“从第一个元素开始，然后一个一个地移动”，那么显然不能有效地实现树搜索。也不能实现二进制搜索。因此，您必须提供确切支持哪些操作的列表，以及(关键是)每个操作的复杂性界限。

您可以借助堆栈将该递归函数转换为迭代函数。

//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循环，许多编译器甚至会为您这样做。

一些更面向数学的递归调用可以通过递归关系来解决。你遇到这些尚未解决的问题的可能性是不太可能的，但它可能会让你感兴趣。

//编辑，性能？真正取决于您的实现和树的大小。如果递归调用有很大的深度，那么您将得到堆栈溢出，而迭代版本将执行得很好。我会更好地掌握递归(如何使用内存)，您应该能够决定哪一个更适合您的情况。下面是用斐波那契数进行这类分析的一个例子。。

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

这是一个关于这个主题的菲尔·哈克( Phil )撰写。

性能的提高无论如何都是推测性的，编译器在幕后对我们的代码所做的事情并不总是可以预测的。实现这两种方法，得到一些实数。如果它们是相似的，请使用您发现更易读的。