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

当前回答

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

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

其他回答

递归函数执行流可以表示为树。 同样的逻辑可以通过循环来实现,循环使用数据结构遍历该树。 深度优先遍历可以使用堆栈完成,宽度优先遍历可以使用队列完成。

所以,答案是肯定的。为什么:https://stackoverflow.com/a/531721/2128327。

任何递归都可以在一个循环中完成吗?是的,因为 图灵机所做的一切都是通过执行一个循环完成的: 获取一条指令, 评估, 转到1。

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

递归不只是在堆栈上调用相同的函数,一旦函数消亡,它就会从堆栈中删除。因此,总是可以使用显式堆栈来管理使用迭代的相同操作的调用。 所以,所有递归代码都可以转换为迭代。

原则上,在数据结构和调用堆栈都具有无限状态的语言中,总是可以删除递归并替换为迭代。这是丘奇-图灵论文的一个基本结论。

Given an actual programming language, the answer is not as obvious. The problem is that it is quite possible to have a language where the amount of memory that can be allocated in the program is limited but where the amount of call stack that can be used is unbounded (32-bit C where the address of stack variables is not accessible). In this case, recursion is more powerful simply because it has more memory it can use; there is not enough explicitly allocatable memory to emulate the call stack. For a detailed discussion on this, see this discussion.

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