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))
当前回答
是否总是可以为每个递归函数编写非递归形式?
是的。一个简单的形式证明是，微递归和非递归演算(如GOTO)都是图灵完备的。由于所有的图灵完备演算在表达能力上是严格等价的，所以所有的递归函数都可以用非递归图灵完备演算来实现。
不幸的是，我无法在网上找到一个好的，正式的GOTO定义，所以这里有一个:
GOTO程序是在寄存器机器上执行的命令序列P，这样P是以下其中之一:
HALT，停止执行 R = R + 1，其中R是任意寄存器 R = R - 1，其中R是任意寄存器 GOTO x，其中x是一个标签 IF r≠0 GOTO x，其中r是任意寄存器，x是一个标签 一个标签，后面跟着上面的任何命令。
然而，递归函数和非递归函数之间的转换并不总是简单的(除非手动重新实现调用堆栈)。
欲了解更多信息，请参阅这个答案。
其他回答
有时候替换递归要简单得多。在20世纪90年代，递归曾经是计算机科学中很流行的东西，所以当时很多普通的开发人员认为，如果你用递归来解决问题，这是一个更好的解决方案。所以他们会使用递归而不是反向循环，或者类似的愚蠢的东西。所以有时候移除递归是一种简单的“这很明显”的练习。
现在这已经不是什么问题了，因为时尚已经转向了其他技术。
递归不只是在堆栈上调用相同的函数，一旦函数消亡，它就会从堆栈中删除。因此，总是可以使用显式堆栈来管理使用迭代的相同操作的调用。 所以，所有递归代码都可以转换为迭代。
消除递归是一个复杂的问题，在定义良好的情况下是可行的。
以下是简单的情况:
尾递归 直接线性递归
可以将任何递归算法转换为非递归算法 一个，但通常逻辑要复杂得多，这样做需要 堆栈的使用。事实上，递归本身使用堆栈:the 函数堆栈。
详情:https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions
这是一个迭代算法:
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
