有什么只能通过递归来实现吗？

我不确定，但我听说过只能通过递归实现的算法。有人知道这样的事情吗？有什么只能通过递归来实现吗？

2010-08-10 Shubham

看看http://stackoverflow.com/questions/1011448/necessary-uses-of-recursion-in-imperative-languages – 2010-08-10 17:03:25

你应该看看下面的问题：http://stackoverflow.com/questions/3451439/is-there-anything-which-can-only-be-by-recursion – 2010-08-10 17:19:29

在命令式语言中？ – 2010-08-10 17:22:35

您需要澄清您正在讨论的递归类型。有算法递归，并且在实现有递归。确实，任何递归的算法都允许简单的非递归实现 - 人们可以通过使用手动堆栈模拟递归的标准技巧来轻松实现。

但是，您的问题仅提供算法。如果我们假定它具体是关于算法递归，那么答案是是，这里有一些固有的和不可避免的递归算法。在一般情况下，不可能用非递归算法替换固有递归算法。构建固有递归算法的最简单方法是首先采用固有递归的数据结构。例如，假设我们需要遍历一棵只有父 - 子链接的树（并且没有子 - 父链接）。想出一个合理的非递归算法来解决这个问题是不可能的。

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

固有递归算法的另一个例子是众所周知的QuickSort算法。 QuickSort始终是递归的，并且它不能简单地转化为非递归算法，因为如果您成功完成此操作，它将不再是QuickSort。这将是一个完全不同的算法。当然，这听起来像纯粹的语义练习，但是这也是值得一提的。

来源

2010-08-10 17:17:11 AnT

你能解释一下“算法递归”是什么意思吗？我从来没有听说过。关于你的快速评论：你是说“常用”（恒定空间）实现不是快速排序，还是算法递归，即使它不是实际递归？ – sepp2k 2010-08-11 08:55:58

*算法递归*（或*递归算法*）我的意思是基于以下原理构建的算法：1）使用分而治之（D＆C）方法，即通过将问题分解为更小的子区域来解决问题， 2）D＆C方法产生的子问题以LIFO顺序解决，即子问题等待轮到他们解决在堆栈状结构中。如果无法通过常数限制该LIFO数据结构的大小，那么该算法本质上是真正的*递归*。 – AnT 2010-08-11 16:28:55

此外，我不知道这样的东西作为恒定空间QuickSort。 QuickSort的智能实现需要'O（log n）'空间。如果我们引入平台限制（比如给定平台上最大数组的大小），我们当然可以用相对较小的常量来限制空间，但这与算法本身没什么关系。 QuickSort仍然（并始终）递归。另外还有深度优先搜索。 – AnT 2010-08-11 16:31:26

如果我正确地记住了我的算法，那么递归无法通过堆栈和循环完成任何操作。然而，我手边没有这方面的正式证据。

编辑：它发生在我身上，答案可能是唯一可以通过递归实现的，不能用堆栈+循环实现的，是堆栈溢出？

来源

2010-08-10 17:01:07 Mark

当然，你可以产生一个没有递归的stackoverflow：创建一个有限容量的堆栈数据结构。现在继续推动该堆栈直到超过容量。堆栈溢出。毕竟，当你有无限递归时，会发生什么（除了容量超出的栈是进程的调用栈而不是你在程序中明确创建的栈）。 – sepp2k 2010-08-10 17:06:10

这是一个笑话，我很抱歉，如果它不好笑。 – Mark 2010-08-10 17:09:13

不，sepp2k似乎已经设置了'senseOfHumor = false;' – AllenG 2010-08-10 17:12:31

您始终可以通过保留自己的堆栈来模拟递归。所以不行。

来源

2010-08-10 17:01:08 sepp2k

任何递归函数也可以转换为等价的迭代函数。 – quantumSoup 2010-08-11 01:26:01

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

摘录：

鉴于递归总体效率较低，我们为什么要使用它？有两种情况下递归是最好的解决办法：

的问题是使用递归更清楚解决：有很多问题，其中递归解决方案更清晰，更清洁和更易懂。只要效率不是主要问题，或者各种解决方案的效率是可比较的，那么您应该使用递归解决方案。
通过递归解决一些问题更容易：有一些问题没有简单的迭代解决方案。在这里你应该使用递归。河内问题塔是一个迭代解决方案非常困难的例子。我们会在本指南后面的章节中看看河内的塔楼。

来源

2010-08-10 17:06:36

你只是在寻找一个递归的实例吗？最近我的朋友和我实现了Haar Wavelet函数（作为开始学习Ruby的练习），这似乎需要递归。除非任何人没有递归实现它？

我会想象任何时候一个人不知道堆栈的深度正在迭代，递归是合乎逻辑的路径。当然，它可能适用于一些被破解的循环，但那是好代码吗？

来源

2010-08-10 17:07:37 David

有什么只能通过递归来实现吗？

回答

相关问题