每个递归都能转换成迭代吗？

Question

每个递归都能转换成迭代吗？

A Reddit线程提出了一个明显有趣的问题：

尾递归函数可以很小地转化为迭代函数。其他的，可以通过使用显式堆栈进行转换。能，会，可以每一，每个递归转化为迭代？

文章中的(计数器？)示例是对：

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

Answer 1

是否总是可以为每个递归函数编写非递归形式？是。一个简单的形式证明就是证明预递归非递归演算(如Goto)都是图灵完整的。由于所有图灵完全计算器在表达能力上都是完全等价的，所以所有递归函数都可以用非递归图灵全演算来实现。不幸的是，我无法找到GotoOnline的一个好的、正式的定义，因此这里有一个：Goto程序是一系列命令P在寄存器机使.P如下之一：HALT，这将停止执行r = r + 1哪里r是任何登记册r = r – 1哪里r是任何登记册GOTO x哪里x是个标签IF r ≠ 0 GOTO x哪里r是任何登记册x是个标签一个标签，后面跟着上面的任何命令。然而，递归函数和非递归函数之间的转换并不总是那么简单(除了调用堆栈的盲目手动重新实现)。有关更多信息，请参见这个答案.

Answer 2

递归在实际的解释器或编译器中被实现为堆栈或类似的结构。因此，您当然可以将递归函数转换为迭代对应函数。因为它总是这样做的(如果是自动的)..您将只是临时地复制编译器的工作，而且可能是以一种非常丑陋和低效的方式复制编译器的工作。