有什么只能通过递归实现的吗?

你需要澄清你所说的是什么样的递归。有 算法的 递归,在 实施 . 确实,任何递归 算法 允许直接非递归 实施 -通过使用手动堆栈模拟递归的标准技巧,可以很容易地做到这一点。

然而,你的问题提到 算法 只有。如果假设它是关于算法递归的,那么答案是 对 有一些算法是固有的和不可避免的递归的。一般情况下,不可能用非递归算法替换固有递归算法。构建固有递归算法的最简单方法是采用固有递归 数据结构 第一。例如,假设我们需要遍历一个只有父到子链接(没有子到父链接)的树。要解决这个问题,不可能提出一个合理的非递归算法。

所以,这就是一个例子:只有父-子链接的树的遍历不能由非递归算法执行。

另一个固有递归算法的例子是众所周知的快速排序算法。快速排序始终是递归的,不能简单地将其转换为非递归算法,因为如果成功执行此操作,它将不再是快速排序。这将是一个完全不同的算法。当然,这听起来像是纯语义的练习,但这也是值得一提的。

您总是可以通过保留自己的堆栈来模拟递归。所以没有。

如果我正确地记住了我的算法,就没有什么递归是不能用堆栈和循环完成的。不过,我手边没有正式的证据。

编辑:我突然想到答案,可能是,堆栈+循环唯一不能通过递归实现的,是堆栈溢出吗?

下面比较递归与非递归实现: http://www.sparknotes.com/cs/recursion/whatisrecursion/section1.html

Excerpt:

鉴于递归通常效率较低,我们为什么要使用它?有两种情况下递归是最佳解决方案:

1. 使用递归可以更清楚地解决这个问题:在许多问题中,递归解决方案更清晰、更清晰、更易于理解。只要效率不是主要问题,或者如果各种解决方案的效率是可比较的,那么您应该使用递归解决方案。
2. 有些问题通过递归更容易解决:有些问题没有简单的迭代解。这里应该使用递归。河内塔问题就是这样一个例子,在这个例子中迭代求解是非常困难的。我们将在本指南的后面部分中介绍河内的塔楼。

你只是在找一个递归的实用例子吗?最近我和我的朋友实施了 Haar Wavelet 函数(作为开始学习Ruby的练习),它似乎需要递归。除非有人不使用递归实现它?

我可以想象,任何时候当一个人不知道一个正在迭代的堆栈的深度时,递归是合乎逻辑的方式。当然,它可以通过一些简单的循环实现,但这是好代码吗?