有删除递归的模式吗？

我有一个完美的算法，但它使用递归。我知道几乎所有东西都有模式，但我无法找到这种情况。有删除递归的模式吗？

我只需要一些简单的例子来说明如何修改算法，特别是方法或函数自己调用的部分。我已经看到了迭代算法，它在while循环中完成。所以必须有一个简单的检查清单，以便将递归算法转换为迭代算法。

您肯定可以使用迭代和自定义调用堆栈对递归进行建模。由于递归只不过是在新环境中执行相同的指令，所以可以使用简单的堆栈结构为自己的环境建模，然后将算法封装在循环中，在迭代开始时推送当前的迷你环境并将其弹出每当完成循环迭代时，或通过break或continue过早退出。

2011-04-25 17:24:54 yan

正确，但确定什么是“当前的微环境”并不总是微不足道的，特别是分支递归。 – Davy8 2011-04-25 17:34:10

顺便说一句，如果您使用的是GCC或llvm，那么打开-O2或-O3的非调试代码将为您执行尾递归消除。（如果你不知道，尾递归是当递归调用是函数中的最后一件事，并且简单地被返回时，即不是表达式的一部分，参见http://en.wikipedia.org/wiki/Tail_call。）

因此，如果递归写出更清晰的阅读，最好坚持下去。

2011-04-25 17:34:29

只需添加，它不是简单地说它是函数中的最后一个东西，但是当调用的返回值不用于创建当前的返回值时。即'return 4 + recur（i）;'不是尾递归的，因为它的返回值仍然用于产生当前的返回值。 – yan 2011-04-25 17:38:41

谢谢你的提醒。 +1。编辑答案反映了这一点。 – 2011-04-25 17:59:28

递归发生在递归发生的尾随递归，因为函数的结束非常微不足道，使得循环无递归。有些编译器甚至会自动为你做。

以系统的方式将任何递归函数转换为迭代函数并不是那么简单，并且很可能最终创建自己的调用堆栈，这很可能会破坏实现非递归算法的目的。

2011-04-25 17:54:12 Davy8

回答