分而治之和递归
我想知道分而治之的技术是否总是将一个问题划分为同一类型的子问题？通过相同类型，我的意思是可以使用递归函数来实现它。分而治之总是可以通过递归来实现吗？
谢谢！
I wonder if the technique of divide and conquer always divide a problem into subproblems of same type? By same type, I mean one can implement it using a function with recursion. Can divide and conquer always be implemented by recursion?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
“总是”是一个可怕的词，但我无法想到不能使用递归的分而治之的情况。根据定义，分而治之会创建与初始问题相同形式的子问题 - 这些子问题不断分解，直到达到某个基本情况，并且划分的数量与输入的大小相关。递归是解决此类问题的自然选择。
请参阅维基百科文章了解更多有用信息。
"Always" is a scary word, but I can't think of a divide-and-conquer situation in which you couldn't use recursion. It is by definition that divide-and-conquer creates subproblems of the same form as the initial problem - these subproblems are continually broken down until some base case is reached, and the number of divisions correlates with the size of the input. Recursion is a natural choice for this kind of problem.
See the Wikipedia article for more good information.
根据定义，分而治之算法是一种可以通过递归解决的算法。所以答案是肯定的。
A Divide-and-conquer algorithm is by definition one that can be solved by recursion. So the answer is yes.
通常，是的！ 合并排序就是一个例子。这是动画版本 相同。
Usually, yes! Merge sort is an example of the same. Here is an animated version of the same.
是的。在分而治之的算法技术中，我们将给定的较大问题划分为较小的子问题。这些较小的子问题必须与较大的问题相似，只是它们的规模较小。
例如，对大小为 N 的数组进行排序的问题与对大小为 N/2 的数组进行排序的问题没有什么不同。只是后一个问题的规模比前一个小。
如果较小的子问题与较大的子问题不相似，则分治技术不能用于解决较大的问题。换句话说，只有当给定的较大问题可以划分为与较大问题相似的较小子问题时，才能使用分而治之技术来解决给定问题。
Yes. In divide and conquer algorithmic technique we divide the given bigger problem into smaller sub-problems. These smaller sub-problems must be similar to the bigger problem except that these are smaller in size.
For example, the problem of sorting an array of size N is no different from the problem of sorting an array of size N/2. Except that the latter problem size is smaller than that of former one.
If the smaller sub-problem is not similar to the bigger one, then the divide and conquer technique can not be used to solve the bigger problem. In other words, a given problem can be solved using divide and conquer technique only iff the given bigger problem can be divided into smaller sub problems which are similar to the bigger problem.
检查合并排序算法就足以解决这个问题。在理解了分而治之（也称为递归）的合并排序算法的实现之后，您将看到如果没有递归，它会变得多么困难。
实际上，这里最重要的是算法的复杂性，它用 big-oh 表示法和归并排序的 nlogn 来表示。
对于归并排序示例，还有另一个版本，称为自下而上归并排序。它是它的简单且非递归版本。
它比典型系统上的递归、自顶向下合并排序慢约 10%。您可以参考以下链接了解更多信息。第三讲已经解释得很清楚了。
https://www.coursera.org/learn/introduction-to-algorithms#< /a>
Examining merge sort algorithm will be enough for this question. After understanding implementation of merge sort algorithm with divide and conquer (also recursion) you will see how difficult it would be making it without recursion.
Actually the most important thing here is the complexity of the algorithm which is expressed with big-oh notation and nlogn for merge sort.
For mergesort exapmle there is another version which is called bottom-up merge sort. It is simple and non-recursive version of it.
it is about 10% slower than recursive, top-down mergesort on typical systems. You can refer to following link for more information. It is explained well in 3rd lecture.
https://www.coursera.org/learn/introduction-to-algorithms#
递归是一种编程方法，您可以根据函数本身来定义函数。该函数通常会调用自身并稍微修改参数（以便收敛）。
Recursion is a programming method where you define a function in terms of itself. The function generally calls itself with slightly modified parameters (in order to converge).
是的，所有分而治之总是使用递归来实现。
典型的分而治之算法使用以下三个步骤解决问题。
以下是一些标准算法，即分而治之算法。
1）二分查找，
2）快速排序，
3）归并排序，
4）施特拉森算法
Yes All Divide and Conquer always be implemented using recursion .
A typical Divide and Conquer algorithm solves a problem using following three steps.
Following are some standard algorithms that are Divide and Conquer algorithms.
1) Binary search,
2) Quick Sort,
3) Merge Sort,
4) Strassen’s Algorithm
想象一下，
P是一个大小为n的问题，而S是解决方案。在这种情况下，如果P足够大，可以分为子问题，例如P1，P2，P3>,P4, ... ,Pk;假设有 k 个子问题，每个 k 个子问题都有 k 个解决方案，例如S1、S2、S3，... ,Sk;现在，如果我们将子问题的每个解组合在一起，我们就可以得到 S 结果。在分而治之的策略中，主要问题是什么，所有子问题都必须相同。例如，如果P已排序，则P1、P2和Pn也必须已排序。这就是它本质上的递归。因此，分而治之将是递归的。Imagine
Pis a problem with size ofnandSis the solution. In this case, ifPis large enough to be divided into sub problem, for exampleP1,P2,P3,P4, ... ,Pk; let say k sub problems and also there would be k solutions for each of k sub problems, likeS1,S2,S3, ... ,Sk; Now if we combine each solutions of sub problem together we can get the S result. In divide and conquer strategy what ever is the main problem all sube problems must be same. For example ifPis sort then theP1,P2andPnmust be sort too. So this is how it is recursive in nature. So, divide and conqure will be recursive.