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

Question

如果没有,是否有一个好的计数器示例显示迭代算法,其中不存在递归对应物？

如果所有迭代算法都可以递归表达,那么在哪些情况下更难以做到这一点？

此外,编程语言在这一切中扮演什么角色？我可以想象,Scheme程序员对Java迭代(=尾递归)和堆栈使用的看法与Java专用程序员不同.

Answer 1

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

Answer 2

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

是的,但证据并不有趣:

1. 其所有的控制流转换程序转换成包含单个case语句的单个循环,其中每个分支是直线控制流可能包括break,return,exit,raise,等.引入一个新变量(称之为"程序计数器"),case语句用它来决定下一个要执行的块.

   这种结构是在20世纪60年代伟大的"结构化编程战争"中发现的,当时人们在争论各种控制流构造的相对表现力.

2. 用递归函数替换循环,并用参数替换每个可变局部变量到该函数.瞧!迭代由递归替换.

此过程相当于为原始函数编写解释器.正如您可能想象的那样,它会导致无法读取的代码,并且这不是一件有趣的事情. 然而,一些技术对于具有命令式编程背景的人来说是有用的,他们正在学习第一次用功能语言编程.

Answer 3

就像你说的,每个迭代方法都可以变成一个"递归"方法,并且通过尾调用,堆栈也不会爆炸.:-)实际上,这实际上是Scheme如何实现所有常见的循环形式.方案示例:

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

在这里,虽然功能看起来迭代的,它实际上在递归内部拉姆达这三个参数,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)))

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

Answer 4

将迭代定义为:

function q(vars):
  while X:
    do Y

可以翻译为:

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

在大多数情况下,Y会包括递增一个由X测试的计数器.当进行递归路由时,这个变量必须以某种方式在'vars'中传递.