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

当前回答

原则上,在数据结构和调用堆栈都具有无限状态的语言中,总是可以删除递归并替换为迭代。这是丘奇-图灵论文的一个基本结论。

Given an actual programming language, the answer is not as obvious. The problem is that it is quite possible to have a language where the amount of memory that can be allocated in the program is limited but where the amount of call stack that can be used is unbounded (32-bit C where the address of stack variables is not accessible). In this case, recursion is more powerful simply because it has more memory it can use; there is not enough explicitly allocatable memory to emulate the call stack. For a detailed discussion on this, see this discussion.

其他回答

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

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

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

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

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

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

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

这是一个迭代算法:

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

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

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

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