所有迭代算法都可以被递归表达吗？

Question

所有的迭代算法都能用递归表达吗？

如果不能，是否存在一个好的反例来展示存在某些迭代算法没有对应的递归算法？

如果所有的迭代算法都能用递归表达，那么是否存在某些情况下更难做到这一点？

编程语言在其中扮演了什么角色？我可以想象Scheme程序员对于迭代（即尾递归）和堆栈使用可能与仅限于Java的程序员有所不同。

- eljenso

---

http://mathoverflow.com/ - jldupont

Answer 1

这个结论有一个简单的即兴证明。因为你可以使用严格迭代结构来构建图灵完备语言，也可以使用仅递归结构的图灵完备语言，所以两者等价。

- plinth

---

哇，发人深省。我羡慕那些比我更快吸收这个信息并点赞的人。是时候好好学习一下了。 - eljenso

等等，那不是一种逻辑谬误吗？循环论证？ - C Bauer

C Bauer: 实际上并不是这样的。证明非常简单：假设有迭代结构的IT语言和有递归结构的REC语言。使用IT模拟通用图灵机，然后使用REC模拟通用图灵机。模拟程序的存在保证了IT和REC都能计算所有可计算函数。在λ演算中已经证明了这个性质，其中所有函数都是部分递归的。 - fishlips

另外，使用严格的（迭代/递归）构建一个图灵完备语言，并在其中编写一个使用严格的（递归/迭代）的图灵完备语言解释器。这样，您编写的任何程序都将同时进行迭代和递归执行！ - David Thornley

Answer 2

所有迭代算法都可以用递归表达，但证明并不有趣：

1.将程序及其所有控制流转换为一个包含单个case语句的循环，其中每个分支都是直线控制流，可能包括break、return、exit、raise等。引入一个新变量（称之为“程序计数器”），case语句使用该变量来决定下一个要执行的块。

这种构造在20世纪60年代的“结构化编程争论”期间被发现，当时人们在争论各种控制流结构的相对表现力。

2.用递归函数替换循环，并将每个可变本地变量替换为该函数的参数。以上。迭代被递归所取代。

此过程等效于编写原始函数的解释器。正如您所想象的那样，它会产生难以阅读的代码，而且这并不是一件有趣的事情。然而，这些技术中的一些对于具有命令式编程背景且首次学习函数式语言的人可能会有用。

- Norman Ramsey

---

哎呀，@Norman，这是一个有趣的事情...对于编译器来说。实际上，过程是：将命令式代码转换为函数式代码，然后将函数式代码转换为命令式代码。为什么这很有趣？因为函数式代码具有简单的语义，但无法执行，而命令式输出难以理解，但适合执行。特别是函数式代码易于优化高级别的东西，而命令式代码易于优化低级别的东西（但最初的混合对于任何目的都很难处理）。 - Yttrill

真正无聊的事情是通过递归函数调用模拟控制原语的语义。虽然有时它们可能会使源代码背后的意图更清晰，但它们经常会使人难以理解它们实际所做的事情，除了在原始上下文中模拟执行。另一方面，对于有经验的用户来说，函数调用具有快速缩减的众所周知的方法。这些差异就像你是否有使用某些方程式（而不是进行所有算术运算）来解决问题的权限。 - FrankHB

Answer 3

就像你说的一样，每个迭代方法都可以变成“递归”方法，并且通过尾调用，堆栈不会爆炸。 :-) 实际上，这正是Scheme实现所有常见循环形式的方式。以下是Scheme的示例：

(define (fib n)
  (do ((x 0 y)
       (y 1 (+ x y))
       (i 1 (+ i 1)))
      ((> i n) x)))

这里，虽然该函数看起来是迭代的，但实际上它在内部使用一个带有三个参数 x、y 和 i 的 lambda 递归，并在每次迭代时使用新值调用自身。

下面是该函数可能被宏展开的一种方式：

(define (fib n)
  (letrec ((inner (lambda (x y i)
                    (if (> i n) x
                        (inner y (+ x y) (+ i 1))))))
    (inner 0 1 1)))

这样，递归的本质更加直观可见。

- C. K. Young

---

请注意，任何迭代算法都可以转化为尾递归算法。例如，只需将其转换为传递续体风格即可。 - Derrick Turk

我只想补充一点，不是每种语言的编译器都会优化尾递归调用，因此在使用尾递归的那些语言中，堆栈确实可能会"爆炸"(溢出)，例如C#。 - dcstraw

Answer 4

将迭代定义为：

function q(vars):
  while X:
    do Y

可以翻译为：

 function q(vars):
    if X:
      do Y
      call q(vars)

在大多数情况下，Y 包括递增由X测试的计数器。当采用递归路径时，必须以某种方式将此变量通过 'vars' 传递。

- Johan

Answer 5

正如plinth在他们的回答中所指出的那样，我们可以构造证明来展示递归和迭代是等价的，并且都可以用来解决同一个问题；然而，尽管我们知道这两者是等价的，但使用其中一种方法可能会有缺点。

在不针对递归进行优化的语言中，您可能会发现使用迭代的算法比递归的算法更快，同样，在经过优化的语言中，您可能会发现使用另一种语言编写的迭代算法比递归算法运行得更快。此外，可能没有明显的方法来使用递归或迭代编写给定的算法，反之亦然。这可能导致代码难以阅读，从而导致可维护性问题。

- rjzii

Answer 6

Prolog是一种仅支持递归的编程语言，你可以在其中做几乎所有的事情（虽然我不建议你这样做，但你可以尝试：））

- dmonlord

Answer 7

递归解决方案通常与迭代解决方案相比，相对低效。 然而，需要注意的是，有些问题只能通过递归来解决，而等效的迭代解决方案可能不存在或者极其复杂难以编写（例如，Ackermann函数无法在没有递归的情况下表达）。虽然递归很优雅，易于编写和理解。

- yogi

---

"Ackermann函数无法在没有递归的情况下表达"这并不正确。你认为计算机如何实现递归？CPU以迭代方式运行一系列指令。为了支持函数调用，包括递归调用，它管理一个栈。使用递归只是让语言（操作系统、运行时等）为您管理堆栈。可以用自己管理堆栈的迭代算法来替换任何递归算法，包括Ackermann函数。 - Mud