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))
当前回答
这是一个迭代算法:
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
其他回答
递归函数执行流可以表示为树。 同样的逻辑可以通过循环来实现，循环使用数据结构遍历该树。 深度优先遍历可以使用堆栈完成，宽度优先遍历可以使用队列完成。
所以，答案是肯定的。为什么:https://stackoverflow.com/a/531721/2128327。
任何递归都可以在一个循环中完成吗?是的,因为 图灵机所做的一切都是通过执行一个循环完成的: 获取一条指令， 评估, 转到1。
有时候替换递归要简单得多。在20世纪90年代，递归曾经是计算机科学中很流行的东西，所以当时很多普通的开发人员认为，如果你用递归来解决问题，这是一个更好的解决方案。所以他们会使用递归而不是反向循环，或者类似的愚蠢的东西。所以有时候移除递归是一种简单的“这很明显”的练习。
现在这已经不是什么问题了，因为时尚已经转向了其他技术。
是的，显式地使用堆栈(但恕我直言，递归读起来要舒服得多)。
递归意味着不管你喜不喜欢，函数都会调用自己。当人们谈论是否可以在没有递归的情况下完成一些事情时，他们的意思是这样的，你不能说“不，这是不对的，因为我不同意递归的定义”是一个有效的陈述。
考虑到这一点，你所说的其他一切都是无稽之谈。你说的另一件不是废话的事情是，你无法想象没有调用栈的编程。这是几十年来一直在做的事情，直到使用调用堆栈变得流行起来。旧版本的FORTRAN缺乏调用堆栈，它们工作得很好。
顺便提一下，有些图灵完备语言只实现递归(例如SML)作为循环的一种手段。也有一些图灵完备语言只是将迭代作为一种循环的手段来实现(例如FORTRAN IV)。丘奇-图灵命题证明了在纯递归语言中任何可能的事情都可以在非递归语言中完成，反之亦然，因为它们都具有图灵完备性。
基本上是的，从本质上讲，你最终不得不做的是将方法调用(隐式地将状态推入堆栈)替换为显式的堆栈推入，以记住“前一个调用”已经到达的位置，然后执行“被调用的方法”。
我可以想象，通过模拟方法调用，循环、堆栈和状态机的组合可以用于所有场景。这是否会“更好”(或者更快，或者在某种意义上更有效)是不可能笼统地说的。
