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))
当前回答
递归函数执行流可以表示为树。 同样的逻辑可以通过循环来实现，循环使用数据结构遍历该树。 深度优先遍历可以使用堆栈完成，宽度优先遍历可以使用队列完成。
所以，答案是肯定的。为什么:https://stackoverflow.com/a/531721/2128327。
任何递归都可以在一个循环中完成吗?是的,因为 图灵机所做的一切都是通过执行一个循环完成的: 获取一条指令， 评估, 转到1。
其他回答
是的，总是可以编写一个非递归的版本。简单的解决方案是使用堆栈数据结构并模拟递归执行。
所有可计算的函数都可以用图灵机计算，因此递归系统和图灵机(迭代系统)是等价的。
递归意味着不管你喜不喜欢，函数都会调用自己。当人们谈论是否可以在没有递归的情况下完成一些事情时，他们的意思是这样的，你不能说“不，这是不对的，因为我不同意递归的定义”是一个有效的陈述。
考虑到这一点，你所说的其他一切都是无稽之谈。你说的另一件不是废话的事情是，你无法想象没有调用栈的编程。这是几十年来一直在做的事情，直到使用调用堆栈变得流行起来。旧版本的FORTRAN缺乏调用堆栈，它们工作得很好。
顺便提一下，有些图灵完备语言只实现递归(例如SML)作为循环的一种手段。也有一些图灵完备语言只是将迭代作为一种循环的手段来实现(例如FORTRAN IV)。丘奇-图灵命题证明了在纯递归语言中任何可能的事情都可以在非递归语言中完成，反之亦然，因为它们都具有图灵完备性。
看看维基百科上的以下条目，你可以把它们作为一个起点，找到你问题的完整答案。
计算机科学中的递归 递归关系
下面一段话可能会给你一些提示，让你知道从哪里开始:
求解递归关系意味着获得一个封闭形式的解:n的非递归函数。
再看看这篇文章的最后一段。
除了显式堆栈之外，另一种将递归转换为迭代的模式是使用蹦床。
在这里，函数要么返回最终结果，要么返回原本执行的函数调用的闭包。然后，初始化(蹦床)函数继续调用返回的闭包，直到达到最终结果。
这种方法适用于相互递归的函数，但恐怕它只适用于尾部调用。
http://en.wikipedia.org/wiki/Trampoline_(电脑)
