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))
当前回答
这是一个迭代算法:
def howmany(x,y)
a = {}
for n in (0..x+y)
for m in (0..n)
a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
end
end
return a[[x,y]]
end
其他回答
是否总是可以为每个递归函数编写非递归形式?
是的。一个简单的形式证明是，微递归和非递归演算(如GOTO)都是图灵完备的。由于所有的图灵完备演算在表达能力上是严格等价的，所以所有的递归函数都可以用非递归图灵完备演算来实现。
不幸的是，我无法在网上找到一个好的，正式的GOTO定义，所以这里有一个:
GOTO程序是在寄存器机器上执行的命令序列P，这样P是以下其中之一:
HALT，停止执行 R = R + 1，其中R是任意寄存器 R = R - 1，其中R是任意寄存器 GOTO x，其中x是一个标签 IF r≠0 GOTO x，其中r是任意寄存器，x是一个标签 一个标签，后面跟着上面的任何命令。
然而，递归函数和非递归函数之间的转换并不总是简单的(除非手动重新实现调用堆栈)。
欲了解更多信息，请参阅这个答案。
你总能把递归函数变成迭代函数吗?没错，如果没记错的话，丘奇-图灵的论文证明了这一点。通俗地说，它指出递归函数可计算的东西也可迭代模型(如图灵机)计算，反之亦然。论文没有精确地告诉你如何进行转换，但它确实说了这是绝对可能的。
在许多情况下，转换递归函数很容易。Knuth在“计算机编程的艺术”中提供了几种技术。通常，递归计算的东西可以用完全不同的方法在更少的时间和空间内计算出来。经典的例子是斐波那契数或其序列。在你的学位计划中，你肯定遇到过这个问题。
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.
归根结底，许多函数以递归形式更容易理解、阅读和编写。除非有令人信服的理由，否则您可能不应该(手动地)将这些函数转换为显式迭代算法。你的计算机将正确地处理这项工作。
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(半开玩笑的)第十定律一样。或者你可能只是找到了一种完全不同的解决方法。但无论如何，肯定是有办法的。
看看维基百科上的以下条目，你可以把它们作为一个起点，找到你问题的完整答案。
计算机科学中的递归 递归关系
下面一段话可能会给你一些提示，让你知道从哪里开始:
求解递归关系意味着获得一个封闭形式的解:n的非递归函数。
再看看这篇文章的最后一段。
有时候替换递归要简单得多。在20世纪90年代，递归曾经是计算机科学中很流行的东西，所以当时很多普通的开发人员认为，如果你用递归来解决问题，这是一个更好的解决方案。所以他们会使用递归而不是反向循环，或者类似的愚蠢的东西。所以有时候移除递归是一种简单的“这很明显”的练习。
现在这已经不是什么问题了，因为时尚已经转向了其他技术。
我想说是的——一个函数调用只不过是一个goto和一个堆栈操作(粗略地说)。您所需要做的就是模仿调用函数时构建的堆栈，并做一些类似于goto的事情(您可以使用没有显式具有此关键字的语言来模仿goto)。
