每个递归都可以转换成迭代吗？ [英] Can every recursion be converted into iteration?

问题描述

reddit主题提出了一个显然有趣的问题：

A reddit thread brought up an apparently interesting question:

尾递归函数可以简单地转换为迭代函数。其他的，可以使用显式堆栈进行转换。可以将每个递归转换为迭代吗？

帖子中的（计数器？）示例是一对：

The (counter?)example in the post is the pair:

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

推荐答案

你能否总是将递归函数转换为迭代函数？是的，绝对的，教会图灵论文证明了它是否有内存服务。在非专业术语中，它表明通过递归函数可计算的是可以通过迭代模型（例如图灵机）计算，反之亦然。论文并没有准确地告诉你如何进行转换，但它确实说它绝对可能。

Can you always turn a recursive function into an iterative one? Yes, absolutely, and the Church-Turing thesis proves it if memory serves. In lay terms, it states that what is computable by recursive functions is computable by an iterative model (such as the Turing machine) and vice versa. The thesis does not tell you precisely how to do the conversion, but it does say that it's definitely possible.

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

In many cases, converting a recursive function is easy. Knuth offers several techniques in "The Art of Computer Programming". And often, a thing computed recursively can be computed by a completely different approach in less time and space. The classic example of this is Fibonacci numbers or sequences thereof. You've surely met this problem in your degree plan.

在这个硬币的另一面，我们当然可以想象一个编程系统如此先进，以至于处理一个递归定义一个公式作为邀请来记忆先前的结果，从而提供速度的好处，而无需告诉计算机确切地在计算具有递归定义的公式时应遵循哪些步骤。 Dijkstra几乎肯定想象过这样一个系统。他花了很长时间试图将实现与编程语言的语义分开。然后，他的非确定性和多处理编程语言在练习专业程序员之上。

On the flip side of this coin, we can certainly imagine a programming system so advanced as to treat a recursive definition of a formula as an invitation to memoize prior results, thus offering the speed benefit without the hassle of telling the computer exactly which steps to follow in the computation of a formula with a recursive definition. Dijkstra almost certainly did imagine such a system. He spent a long time trying to separate the implementation from the semantics of a programming language. Then again, his non-deterministic and multiprocessing programming languages are in a league above the practicing professional programmer.

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

In the final analysis, many functions are just plain easier to understand, read, and write in recursive form. Unless there's a compelling reason, you probably shouldn't (manually) convert these functions to an explicitly iterative algorithm. Your computer will handle that job correctly.

我可以看到一个令人信服的理由。假设你有一个超高级语言的原型系统，如[穿石棉内衣] Scheme，Lisp，Haskell，OCaml，Perl或Pascal。假设您需要使用C或Java实现的条件。 （也许是政治。）然后你肯定会有一些递归编写的函数，但从字面上翻译，会爆炸你的运行时系统。例如，在Scheme中可以进行无限尾递归，但是相同的习惯用法会导致现有C环境出现问题。另一个例子是使用词法嵌套函数和静态范围，Pascal支持但C不支持。

I can see one compelling reason. Suppose you've a prototype system in a super-high level language like [donning asbestos underwear] Scheme, Lisp, Haskell, OCaml, Perl, or Pascal. Suppose conditions are such that you need an implementation in C or Java. (Perhaps it's politics.) Then you could certainly have some functions written recursively but which, translated literally, would explode your runtime system. For example, infinite tail recursion is possible in Scheme, but the same idiom causes a problem for existing C environments. Another example is the use of lexically nested functions and static scope, which Pascal supports but C doesn't.

在这种情况下，你可能会试图克服政治阻力原始语言。你可能会发现自己重新实现了Lisp，就像Greenspun（诙谐的）第十条法则那样。或者您可能只是找到一种完全不同的解决方案。但无论如何，肯定有办法。

In these circumstances, you might try to overcome political resistance to the original language. You might find yourself reimplementing Lisp badly, as in Greenspun's (tongue-in-cheek) tenth law. Or you might just find a completely different approach to solution. But in any event, there is surely a way.

这篇关于每个递归都可以转换成迭代吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！