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
其他回答
是的，显式地使用堆栈(但恕我直言，递归读起来要舒服得多)。
看看维基百科上的以下条目，你可以把它们作为一个起点，找到你问题的完整答案。
计算机科学中的递归 递归关系
下面一段话可能会给你一些提示，让你知道从哪里开始:
求解递归关系意味着获得一个封闭形式的解:n的非递归函数。
再看看这篇文章的最后一段。
递归函数执行流可以表示为树。 同样的逻辑可以通过循环来实现，循环使用数据结构遍历该树。 深度优先遍历可以使用堆栈完成，宽度优先遍历可以使用队列完成。
所以，答案是肯定的。为什么:https://stackoverflow.com/a/531721/2128327。
任何递归都可以在一个循环中完成吗?是的,因为 图灵机所做的一切都是通过执行一个循环完成的: 获取一条指令， 评估, 转到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
