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)。

消除递归是一个复杂的问题,在定义良好的情况下是可行的。

以下是简单的情况:

尾递归 直接线性递归

除了显式堆栈之外,另一种将递归转换为迭代的模式是使用蹦床。

在这里,函数要么返回最终结果,要么返回原本执行的函数调用的闭包。然后,初始化(蹦床)函数继续调用返回的闭包,直到达到最终结果。

这种方法适用于相互递归的函数,但恐怕它只适用于尾部调用。

http://en.wikipedia.org/wiki/Trampoline_(电脑)

递归函数执行流可以表示为树。 同样的逻辑可以通过循环来实现,循环使用数据结构遍历该树。 深度优先遍历可以使用堆栈完成,宽度优先遍历可以使用队列完成。

所以,答案是肯定的。为什么:https://stackoverflow.com/a/531721/2128327。

任何递归都可以在一个循环中完成吗?是的,因为 图灵机所做的一切都是通过执行一个循环完成的: 获取一条指令, 评估, 转到1。