reddit上的一个帖子提出了一个很有趣的问题:
尾递归函数可以简单地转换为迭代函数。其他的可以通过使用显式堆栈进行转换。每个递归都能转化为迭代吗?
文章中的(counter?)例子是:
(define (num-ways x y)
(case ((= x 0) 1)
((= y 0) 1)
(num-ways2 x y) ))
(define (num-ways2 x y)
(+ (num-ways (- x 1) y)
(num-ways x (- y 1))
当前回答
是的，总是可以编写一个非递归的版本。简单的解决方案是使用堆栈数据结构并模拟递归执行。
其他回答
所有可计算的函数都可以用图灵机计算，因此递归系统和图灵机(迭代系统)是等价的。
是否总是可以为每个递归函数编写非递归形式?
是的。一个简单的形式证明是，微递归和非递归演算(如GOTO)都是图灵完备的。由于所有的图灵完备演算在表达能力上是严格等价的，所以所有的递归函数都可以用非递归图灵完备演算来实现。
不幸的是，我无法在网上找到一个好的，正式的GOTO定义，所以这里有一个:
GOTO程序是在寄存器机器上执行的命令序列P，这样P是以下其中之一:
HALT，停止执行 R = R + 1，其中R是任意寄存器 R = R - 1，其中R是任意寄存器 GOTO x，其中x是一个标签 IF r≠0 GOTO x，其中r是任意寄存器，x是一个标签 一个标签，后面跟着上面的任何命令。
然而，递归函数和非递归函数之间的转换并不总是简单的(除非手动重新实现调用堆栈)。
欲了解更多信息，请参阅这个答案。
递归函数执行流可以表示为树。 同样的逻辑可以通过循环来实现，循环使用数据结构遍历该树。 深度优先遍历可以使用堆栈完成，宽度优先遍历可以使用队列完成。
所以，答案是肯定的。为什么:https://stackoverflow.com/a/531721/2128327。
任何递归都可以在一个循环中完成吗?是的,因为 图灵机所做的一切都是通过执行一个循环完成的: 获取一条指令， 评估, 转到1。
递归在实际解释器或编译器中以堆栈或类似结构的形式实现。因此，您当然可以将递归函数转换为迭代函数，因为这就是它总是这样做的(如果是自动的)。您只是在以一种特别的方式复制编译器的工作，而且可能是一种非常丑陋和低效的方式。
除了显式堆栈之外，另一种将递归转换为迭代的模式是使用蹦床。
在这里，函数要么返回最终结果，要么返回原本执行的函数调用的闭包。然后，初始化(蹦床)函数继续调用返回的闭包，直到达到最终结果。
这种方法适用于相互递归的函数，但恐怕它只适用于尾部调用。
http://en.wikipedia.org/wiki/Trampoline_(电脑)
