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))

当前回答

除了显式堆栈之外,另一种将递归转换为迭代的模式是使用蹦床。

在这里,函数要么返回最终结果,要么返回原本执行的函数调用的闭包。然后,初始化(蹦床)函数继续调用返回的闭包,直到达到最终结果。

这种方法适用于相互递归的函数,但恐怕它只适用于尾部调用。

http://en.wikipedia.org/wiki/Trampoline_(电脑)

其他回答

是的,显式地使用堆栈(但恕我直言,递归读起来要舒服得多)。

是的,总是可以编写一个非递归的版本。简单的解决方案是使用堆栈数据结构并模拟递归执行。

递归在实际解释器或编译器中以堆栈或类似结构的形式实现。因此,您当然可以将递归函数转换为迭代函数,因为这就是它总是这样做的(如果是自动的)。您只是在以一种特别的方式复制编译器的工作,而且可能是一种非常丑陋和低效的方式。

基本上是的,从本质上讲,你最终不得不做的是将方法调用(隐式地将状态推入堆栈)替换为显式的堆栈推入,以记住“前一个调用”已经到达的位置,然后执行“被调用的方法”。

我可以想象,通过模拟方法调用,循环、堆栈和状态机的组合可以用于所有场景。这是否会“更好”(或者更快,或者在某种意义上更有效)是不可能笼统地说的。

有时候替换递归要简单得多。在20世纪90年代,递归曾经是计算机科学中很流行的东西,所以当时很多普通的开发人员认为,如果你用递归来解决问题,这是一个更好的解决方案。所以他们会使用递归而不是反向循环,或者类似的愚蠢的东西。所以有时候移除递归是一种简单的“这很明显”的练习。

现在这已经不是什么问题了,因为时尚已经转向了其他技术。