每个递归都可以转换为迭代吗？
一个reddit线程提出了一个显然有趣的问题：
尾递归函数可以平凡地转换为迭代函数。 其他的，可以通过使用显式堆栈进行转换。 每个递归都可以转化为迭代吗？
帖子中的（counter？）例子是一对：
(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))
你能不能总是把递归函数变成迭代函数？ 是的，绝对的，如果记忆服务的话，教会 - 图灵论文证明了这一点。 从根本上说，它指出递归函数可计算的是迭代模型（例如图灵机）可计算的，反之亦然。 该论文并没有准确地告诉你如何进行转换，但它确实表示这绝对有可能。
在许多情况下，转换递归函数很容易。 Knuth在“计算机编程艺术”中提供了几种技巧。 通常，递归计算的东西可以通过完全不同的方法在更短的时间和空间中计算出来。 这种经典的例子是斐波纳契数字或其序列。 你的学位计划肯定会遇到这个问题。
在这个硬币的另一面，我们当然可以想象一个编程系统如此先进以至于将公式的递归定义作为对先前结果进行记忆的邀请，从而提供速度优势，而无需告知计算机确切地知道哪些步骤请按照递归定义计算公式。 迪杰斯特拉几乎肯定会想到这样一个系统。 他花了很长时间试图将实现从编程语言的语义中分离出来。 再次，他的非确定性和多处理编程语言在专业程序员之上。
归根结底，许多函数只是简单易懂，以递归形式来理解，读取和写入。 除非有令人信服的理由，否则您可能不应该（手动）将这些函数转换为明确的迭代算法。 你的电脑会正确处理这项工作。
我可以看到一个令人信服的理由。 假设你有一个超级高级语言的原型系统，如[穿石棉内衣] Scheme，Lisp，Haskell，OCaml，Perl或Pascal。 假设条件是你需要用C或Java实现的。 （也许是政治。）那么你当然可以递归地写一些函数，但是，从字面上来看，这会翻译你的运行时系统。 例如，Scheme中可能有无限的尾递归，但是相同的习惯用法会导致现有C环境出现问题。 另一个例子是使用词法嵌套函数和静态作用域，Pascal支持但C不支持。
在这种情况下，你可能会试图克服对原始语言的政治抵制。 你可能会发现自己很难重新实现Lisp，就像在Greenspun的（口舌）第十定律中一样。 或者您可能会发现一种完全不同的解决方案。 但无论如何，肯定有办法。
对于每个递归函数总是可以写一个非递归形式吗？
是。 一个简单的形式化证明就是证明μ递归和非递归演算（如GOTO）都是图灵完备的。 由于所有图灵完整的计算结果在表达能力上是严格等价的，所以所有的递归函数都可以通过非递归图灵完全演算来实现。
不幸的是，我无法在网上找到一个好的，正式的GOTO定义，所以这里有一个：
GOTO程序是在注册机器上执行的一系列命令P，使得P是以下之一：
HALT ，暂停执行 r = r + 1其中r是任何寄存器 r = r – 1其中r是任何寄存器 GOTO x其中x是标签 IF r ≠ 0 GOTO x其中r是任何寄存器， x是标签 然而，递归函数和非递归函数之间的转换并不总是微不足道的（除非通过无意识的手动重新实现调用堆栈）。
递归实现为实际解释器或编译器中的堆栈或类似构造。 所以你当然可以将递归函数转换为迭代函数， 因为它总是这样做的（如果是自动的） 。 你只需要以特别的方式复制编译器的工作，并且可能以非常丑陋和低效的方式进行。
链接地址: http://www.djcxy.com/p/53483.html