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))
当前回答
基本上是的，从本质上讲，你最终不得不做的是将方法调用(隐式地将状态推入堆栈)替换为显式的堆栈推入，以记住“前一个调用”已经到达的位置，然后执行“被调用的方法”。
我可以想象，通过模拟方法调用，循环、堆栈和状态机的组合可以用于所有场景。这是否会“更好”(或者更快，或者在某种意义上更有效)是不可能笼统地说的。
其他回答
看看维基百科上的以下条目，你可以把它们作为一个起点，找到你问题的完整答案。
计算机科学中的递归 递归关系
下面一段话可能会给你一些提示，让你知道从哪里开始:
求解递归关系意味着获得一个封闭形式的解:n的非递归函数。
再看看这篇文章的最后一段。
消除递归是一个复杂的问题，在定义良好的情况下是可行的。
以下是简单的情况:
尾递归 直接线性递归
基本上是的，从本质上讲，你最终不得不做的是将方法调用(隐式地将状态推入堆栈)替换为显式的堆栈推入，以记住“前一个调用”已经到达的位置，然后执行“被调用的方法”。
我可以想象，通过模拟方法调用，循环、堆栈和状态机的组合可以用于所有场景。这是否会“更好”(或者更快，或者在某种意义上更有效)是不可能笼统地说的。
原则上，在数据结构和调用堆栈都具有无限状态的语言中，总是可以删除递归并替换为迭代。这是丘奇-图灵论文的一个基本结论。
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)。
