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。

其他回答

我想说是的——一个函数调用只不过是一个goto和一个堆栈操作(粗略地说)。您所需要做的就是模仿调用函数时构建的堆栈,并做一些类似于goto的事情(您可以使用没有显式具有此关键字的语言来模仿goto)。

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

可以将任何递归算法转换为非递归算法 一个,但通常逻辑要复杂得多,这样做需要 堆栈的使用。事实上,递归本身使用堆栈:the 函数堆栈。

详情:https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions

看看维基百科上的以下条目,你可以把它们作为一个起点,找到你问题的完整答案。

计算机科学中的递归 递归关系

下面一段话可能会给你一些提示,让你知道从哪里开始:

求解递归关系意味着获得一个封闭形式的解:n的非递归函数。

再看看这篇文章的最后一段。

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

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