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))
基本上是的，从本质上讲，你最终不得不做的是将方法调用(隐式地将状态推入堆栈)替换为显式的堆栈推入，以记住“前一个调用”已经到达的位置，然后执行“被调用的方法”。
我可以想象，通过模拟方法调用，循环、堆栈和状态机的组合可以用于所有场景。这是否会“更好”(或者更快，或者在某种意义上更有效)是不可能笼统地说的。
递归在实际解释器或编译器中以堆栈或类似结构的形式实现。因此，您当然可以将递归函数转换为迭代函数，因为这就是它总是这样做的(如果是自动的)。您只是在以一种特别的方式复制编译器的工作，而且可能是一种非常丑陋和低效的方式。
除了显式堆栈之外，另一种将递归转换为迭代的模式是使用蹦床。
在这里，函数要么返回最终结果，要么返回原本执行的函数调用的闭包。然后，初始化(蹦床)函数继续调用返回的闭包，直到达到最终结果。
这种方法适用于相互递归的函数，但恐怕它只适用于尾部调用。
http://en.wikipedia.org/wiki/Trampoline_(电脑)
这是一个迭代算法:
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
有时候替换递归要简单得多。在20世纪90年代，递归曾经是计算机科学中很流行的东西，所以当时很多普通的开发人员认为，如果你用递归来解决问题，这是一个更好的解决方案。所以他们会使用递归而不是反向循环，或者类似的愚蠢的东西。所以有时候移除递归是一种简单的“这很明显”的练习。
现在这已经不是什么问题了，因为时尚已经转向了其他技术。
你总能把递归函数变成迭代函数吗?没错，如果没记错的话，丘奇-图灵的论文证明了这一点。通俗地说，它指出递归函数可计算的东西也可迭代模型(如图灵机)计算，反之亦然。论文没有精确地告诉你如何进行转换，但它确实说了这是绝对可能的。
在许多情况下，转换递归函数很容易。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(半开玩笑的)第十定律一样。或者你可能只是找到了一种完全不同的解决方法。但无论如何，肯定是有办法的。
原则上，在数据结构和调用堆栈都具有无限状态的语言中，总是可以删除递归并替换为迭代。这是丘奇-图灵论文的一个基本结论。
Given an actual programming language, the answer is not as obvious. The problem is that it is quite possible to have a language where the amount of memory that can be allocated in the program is limited but where the amount of call stack that can be used is unbounded (32-bit C where the address of stack variables is not accessible). In this case, recursion is more powerful simply because it has more memory it can use; there is not enough explicitly allocatable memory to emulate the call stack. For a detailed discussion on this, see this discussion.
我想说是的——一个函数调用只不过是一个goto和一个堆栈操作(粗略地说)。您所需要做的就是模仿调用函数时构建的堆栈，并做一些类似于goto的事情(您可以使用没有显式具有此关键字的语言来模仿goto)。
看看维基百科上的以下条目，你可以把它们作为一个起点，找到你问题的完整答案。
计算机科学中的递归 递归关系
下面一段话可能会给你一些提示，让你知道从哪里开始:
求解递归关系意味着获得一个封闭形式的解:n的非递归函数。
再看看这篇文章的最后一段。
是否总是可以为每个递归函数编写非递归形式?
是的。一个简单的形式证明是，微递归和非递归演算(如GOTO)都是图灵完备的。由于所有的图灵完备演算在表达能力上是严格等价的，所以所有的递归函数都可以用非递归图灵完备演算来实现。
不幸的是，我无法在网上找到一个好的，正式的GOTO定义，所以这里有一个:
GOTO程序是在寄存器机器上执行的命令序列P，这样P是以下其中之一:
HALT，停止执行 R = R + 1，其中R是任意寄存器 R = R - 1，其中R是任意寄存器 GOTO x，其中x是一个标签 IF r≠0 GOTO x，其中r是任意寄存器，x是一个标签 一个标签，后面跟着上面的任何命令。
然而，递归函数和非递归函数之间的转换并不总是简单的(除非手动重新实现调用堆栈)。
欲了解更多信息，请参阅这个答案。
递归意味着不管你喜不喜欢，函数都会调用自己。当人们谈论是否可以在没有递归的情况下完成一些事情时，他们的意思是这样的，你不能说“不，这是不对的，因为我不同意递归的定义”是一个有效的陈述。
考虑到这一点，你所说的其他一切都是无稽之谈。你说的另一件不是废话的事情是，你无法想象没有调用栈的编程。这是几十年来一直在做的事情，直到使用调用堆栈变得流行起来。旧版本的FORTRAN缺乏调用堆栈，它们工作得很好。
顺便提一下，有些图灵完备语言只实现递归(例如SML)作为循环的一种手段。也有一些图灵完备语言只是将迭代作为一种循环的手段来实现(例如FORTRAN IV)。丘奇-图灵命题证明了在纯递归语言中任何可能的事情都可以在非递归语言中完成，反之亦然，因为它们都具有图灵完备性。
递归函数执行流可以表示为树。 同样的逻辑可以通过循环来实现，循环使用数据结构遍历该树。 深度优先遍历可以使用堆栈完成，宽度优先遍历可以使用队列完成。
所以，答案是肯定的。为什么:https://stackoverflow.com/a/531721/2128327。
任何递归都可以在一个循环中完成吗?是的,因为 图灵机所做的一切都是通过执行一个循环完成的: 获取一条指令， 评估, 转到1。
可以将任何递归算法转换为非递归算法 一个，但通常逻辑要复杂得多，这样做需要 堆栈的使用。事实上，递归本身使用堆栈:the 函数堆栈。
详情:https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions
递归不只是在堆栈上调用相同的函数，一旦函数消亡，它就会从堆栈中删除。因此，总是可以使用显式堆栈来管理使用迭代的相同操作的调用。 所以，所有递归代码都可以转换为迭代。
