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))
当前回答
我想说是的——一个函数调用只不过是一个goto和一个堆栈操作(粗略地说)。您所需要做的就是模仿调用函数时构建的堆栈，并做一些类似于goto的事情(您可以使用没有显式具有此关键字的语言来模仿goto)。
其他回答
我想说是的——一个函数调用只不过是一个goto和一个堆栈操作(粗略地说)。您所需要做的就是模仿调用函数时构建的堆栈，并做一些类似于goto的事情(您可以使用没有显式具有此关键字的语言来模仿goto)。
所有可计算的函数都可以用图灵机计算，因此递归系统和图灵机(迭代系统)是等价的。
是的，总是可以编写一个非递归的版本。简单的解决方案是使用堆栈数据结构并模拟递归执行。
有时候替换递归要简单得多。在20世纪90年代，递归曾经是计算机科学中很流行的东西，所以当时很多普通的开发人员认为，如果你用递归来解决问题，这是一个更好的解决方案。所以他们会使用递归而不是反向循环，或者类似的愚蠢的东西。所以有时候移除递归是一种简单的“这很明显”的练习。
现在这已经不是什么问题了，因为时尚已经转向了其他技术。
递归意味着不管你喜不喜欢，函数都会调用自己。当人们谈论是否可以在没有递归的情况下完成一些事情时，他们的意思是这样的，你不能说“不，这是不对的，因为我不同意递归的定义”是一个有效的陈述。
考虑到这一点，你所说的其他一切都是无稽之谈。你说的另一件不是废话的事情是，你无法想象没有调用栈的编程。这是几十年来一直在做的事情，直到使用调用堆栈变得流行起来。旧版本的FORTRAN缺乏调用堆栈，它们工作得很好。
顺便提一下，有些图灵完备语言只实现递归(例如SML)作为循环的一种手段。也有一些图灵完备语言只是将迭代作为一种循环的手段来实现(例如FORTRAN IV)。丘奇-图灵命题证明了在纯递归语言中任何可能的事情都可以在非递归语言中完成，反之亦然，因为它们都具有图灵完备性。
