编程语言-所有迭代算法都可以递归表示吗？
如果不是，是否有一个很好的反例显示迭代算法，而该算法不存在递归对应项？
如果是所有迭代算法都可以递归表示的情况，那么在这种情况下是否更难做到？
另外，编程语言在所有这一切中起什么作用？ 我可以想象，Scheme程序员在迭代（=尾递归）和堆栈使用方面与纯Java程序员不同。
有一个简单的临时证明。 由于您可以使用严格的迭代结构构建图灵完整的语言，而仅使用递归结构构建Turning完整的语言，因此两者是等效的。
所有迭代算法都可以递归表示吗？
是的，但证明并不有趣：
将程序及其所有控制流转换为包含单个case语句的单个循环，其中每个分支都是直线控制流，可能包括
break、return、2974257165965460460、raise等。 引入一个新的变量（称为“程序计数器”），case语句使用该变量来确定接下来要执行哪个块。这种构造是在1960年代的巨大“结构化编程大战”期间发现的，当时人们在争论各种控制流构造的相对表达能力。
用递归函数替换循环，并用该函数的参数替换每个可变局部变量。 瞧！ 迭代由递归代替。
此过程相当于为原始功能编写解释器。 就像您想象的那样，它会导致代码无法读取，这并不是一件有趣的事情。 但是，某些技术对于具有强制性编程背景的人来说是很有用的，该人是第一次学习使用功能语言进行编程。
就像您说的那样，每种迭代方法都可以变成一种“递归”方法，并且通过尾部调用，堆栈也不会爆炸。 :-)实际上，这就是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)))
这样，递归性质在视觉上变得更加明显。
将迭代定义为：
function q(vars):
while X:
do Y
可以翻译为：
function q(vars):
if X:
do Y
call q(vars)
在大多数情况下，Y将包括递增由X测试的计数器。在执行递归路由时，必须以某种方式在“ vars”中传递此变量。
正如plinth在他们的答案中指出的那样，我们可以构建证明递归和迭代如何等效的证明，并且都可以用来解决相同的问题。 但是，即使我们知道两者是等效的，但使用一个相对于另一个存在缺点。
在未针对递归进行优化的语言中，您可能会发现使用迭代预执行的算法比递归预执行要快，同样，即使在优化语言中，您也可能会发现使用以另一种语言编写的迭代的算法要比递归执行得更快。 此外，可能没有明显的方式使用递归与迭代来编写给定算法，反之亦然。 这可能导致难以阅读的代码导致可维护性问题。
Prolog仅是递归语言，您可以使用它进行几乎所有的操作（我不建议您这样做，但是您可以:)）
与迭代解决方案相比，递归解决方案通常效率相对较低。但是，需要注意的是，有些问题只能通过递归来解决，并且等效的迭代解决方案可能不存在或非常容易编程（例如，没有递归就无法表达Ackermann函数），尽管递归优雅，容易 写和理解。