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))
当前回答
消除递归是一个复杂的问题，在定义良好的情况下是可行的。
以下是简单的情况:
尾递归 直接线性递归
其他回答
递归意味着不管你喜不喜欢，函数都会调用自己。当人们谈论是否可以在没有递归的情况下完成一些事情时，他们的意思是这样的，你不能说“不，这是不对的，因为我不同意递归的定义”是一个有效的陈述。
考虑到这一点，你所说的其他一切都是无稽之谈。你说的另一件不是废话的事情是，你无法想象没有调用栈的编程。这是几十年来一直在做的事情，直到使用调用堆栈变得流行起来。旧版本的FORTRAN缺乏调用堆栈，它们工作得很好。
顺便提一下，有些图灵完备语言只实现递归(例如SML)作为循环的一种手段。也有一些图灵完备语言只是将迭代作为一种循环的手段来实现(例如FORTRAN IV)。丘奇-图灵命题证明了在纯递归语言中任何可能的事情都可以在非递归语言中完成，反之亦然，因为它们都具有图灵完备性。
递归不只是在堆栈上调用相同的函数，一旦函数消亡，它就会从堆栈中删除。因此，总是可以使用显式堆栈来管理使用迭代的相同操作的调用。 所以，所有递归代码都可以转换为迭代。
是的，显式地使用堆栈(但恕我直言，递归读起来要舒服得多)。
这是一个迭代算法:
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
你总能把递归函数变成迭代函数吗?没错，如果没记错的话，丘奇-图灵的论文证明了这一点。通俗地说，它指出递归函数可计算的东西也可迭代模型(如图灵机)计算，反之亦然。论文没有精确地告诉你如何进行转换，但它确实说了这是绝对可能的。
在许多情况下，转换递归函数很容易。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(半开玩笑的)第十定律一样。或者你可能只是找到了一种完全不同的解决方法。但无论如何，肯定是有办法的。
