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))
当前回答
原则上，在数据结构和调用堆栈都具有无限状态的语言中，总是可以删除递归并替换为迭代。这是丘奇-图灵论文的一个基本结论。
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.
其他回答
递归不只是在堆栈上调用相同的函数，一旦函数消亡，它就会从堆栈中删除。因此，总是可以使用显式堆栈来管理使用迭代的相同操作的调用。 所以，所有递归代码都可以转换为迭代。
原则上，在数据结构和调用堆栈都具有无限状态的语言中，总是可以删除递归并替换为迭代。这是丘奇-图灵论文的一个基本结论。
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.
这是一个迭代算法:
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
是的，显式地使用堆栈(但恕我直言，递归读起来要舒服得多)。
可以将任何递归算法转换为非递归算法 一个，但通常逻辑要复杂得多，这样做需要 堆栈的使用。事实上，递归本身使用堆栈:the 函数堆栈。
详情:https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions
