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

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

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