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

其他回答

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

以下是简单的情况:

尾递归 直接线性递归

基本上是的,从本质上讲,你最终不得不做的是将方法调用(隐式地将状态推入堆栈)替换为显式的堆栈推入,以记住“前一个调用”已经到达的位置,然后执行“被调用的方法”。

我可以想象,通过模拟方法调用,循环、堆栈和状态机的组合可以用于所有场景。这是否会“更好”(或者更快,或者在某种意义上更有效)是不可能笼统地说的。

递归不只是在堆栈上调用相同的函数,一旦函数消亡,它就会从堆栈中删除。因此,总是可以使用显式堆栈来管理使用迭代的相同操作的调用。 所以,所有递归代码都可以转换为迭代。

这是一个迭代算法:

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end

所有可计算的函数都可以用图灵机计算,因此递归系统和图灵机(迭代系统)是等价的。