48

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

如果是所有迭代算法都可以递归表示的情况，有没有更难做到的情况？

另外，编程语言在这一切中扮演什么角色？我可以想象，与纯 Java 程序员相比，Scheme 程序员对迭代（=尾递归）和堆栈使用有不同的看法。

4

7 回答 7

81

有一个简单的临时证明。由于您可以使用严格的迭代结构来构建图灵完备的语言和仅使用递归结构的图灵完备的语言，因此两者是等价的。

于 2010-01-19T13:20:02.253 回答
21

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

是的，但证明并不有趣：

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

    这种结构是在 1960 年代伟大的“结构化编程战争”中发现的，当时人们正在争论各种控制流结构的相对表达能力。

  2. 将循环替换为递归函数，并将每个可变局部变量替换为该函数的参数。瞧！迭代替换为递归。

这个过程相当于为原始函数编写一个解释器。正如您可能想象的那样，它会导致代码不可读，并且这不是一件有趣的事情。 但是，对于具有命令式编程背景且第一次学习使用函数式语言进行编程的人来说，其中一些技术可能很有用。

于 2010-01-19T21:08:20.727 回答
8

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

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

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

这是函数可以被宏扩展的一种方式：

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

这样，递归性质在视觉上变得更加明显。

于 2010-01-19T13:22:08.087 回答
7

将迭代定义为：

function q(vars):
  while X:
    do Y

可以翻译为：

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

在大多数情况下，Y 将包括增加一个由 X 测试的计数器。当走递归路线时，这个变量必须以某种方式在“vars”中传递。

于 2010-01-19T13:23:19.063 回答
1

正如 plinth 在他们的回答中所指出的，我们可以构建证明，证明递归和迭代是如何等效的，并且都可以用来解决相同的问题；然而，即使我们知道这两者是等价的，使用其中一个也有缺点。

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

于 2010-01-19T13:46:10.760 回答
-2

Prolog 是唯一的递归语言，您可以在其中做几乎所有事情（我不建议您这样做，但您可以:)）

于 2010-01-19T13:24:01.483 回答
-4

与迭代解决方案相比，递归解决方案通常效率相对较低。但是，需要注意的是，有些问题只能通过递归来解决，并且可能不存在等效的迭代解决方案，或者编程起来非常复杂（例如The Ackermann function cannot be expression without recursion）虽然递归很优雅，但很容易写和理解。

于 2013-11-14T01:53:41.183 回答