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

问题描述

reddit 帖子 提出了一个明显有趣的问题:

A reddit thread brought up an apparently interesting question:

尾递归函数可以简单地转换为迭代函数.其他的，可以通过使用显式堆栈进行转换.每个递归都可以转化为迭代吗?

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?

帖子中的(计数器?)例子是一对:

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

推荐答案

你能总是把递归函数变成迭代函数吗?是的，绝对的，如果没有记错的话，Church-Turing 论文证明了这一点.通俗地说，它指出递归函数可计算的内容可由迭代模型(例如图灵机)计算，反之亦然.该论文没有准确地告诉您如何进行转换，但它确实说这绝对是可能的.

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屋！