language-agnostic - 每个递归都可以转化为迭代吗？

Question

一个reddit thread提出了一个显然很有趣的问题:

Tail recursive functions can trivially be converted into iterative functions. Other ones, can be transformed by using an explicit stack. Can every recursion be transformed into iteration?

帖子中的(反？)示例是一对:

(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))

Answer 1

你总能把递归函数变成迭代函数吗？是的，绝对如此，如果没记错的话，丘奇-图灵论文证明了这一点。通俗地说，它指出可以通过递归函数计算的东西也可以通过迭代模型(例如图灵机)计算，反之亦然。论文没有确切地告诉你如何进行转换，但它确实说这绝对是可能的。

在许多情况下，转换递归函数很容易。 Knuth 在《计算机编程的艺术》中提供了多种技术。通常，递归计算的事物可以通过完全不同的方法在更少的时间和空间内计算。典型的例子是斐波那契数或其序列。您在学位计划中肯定遇到过这个问题。

另一方面，我们当然可以想象一个如此先进的编程系统，可以将公式的递归定义视为内存先前结果的邀请，从而提供速度优势，而无需准确告诉计算机的麻烦计算具有递归定义的公式时应遵循哪些步骤。迪杰斯特拉几乎肯定确实想象过这样一个系统。他花了很长时间试图将编程语言的实现与语义分开。话又说回来，他的非确定性和多处理编程语言比实践中的专业程序员高出一筹。

归根结底，许多函数以递归形式更容易理解、阅读和编写。除非有令人信服的理由，否则您可能不应该(手动)将这些函数转换为显式迭代算法。您的计算机将正确处理该作业。

我可以看到一个令人信服的理由。假设您有一个超高级语言的原型(prototype)系统，例如[穿石棉内衣]Scheme、Lisp、Haskell、OCaml、Perl 或 Pascal。假设您需要用 C 或 Java 实现。 (也许这是政治。)那么你当然可以递归地编写一些函数，但从字面上翻译，这些函数会爆炸你的运行时系统。例如，Scheme 中可以实现无限尾递归，但相同的习惯用法会给现有 C 环境带来问题。另一个例子是使用词法嵌套函数和静态作用域，Pascal 支持但 C 不支持。

在这些情况下，您可能会尝试克服对原始语言的政治阻力。你可能会发现自己重新实现 Lisp 很糟糕，就像格林斯潘(半开玩笑的)第十定律一样。或者您可能只是找到一种完全不同的解决方案。但无论如何，肯定有办法。