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!
8 Answers
"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.
Yes All Divide and Conquer always be implemented using recursion .
A typical Divide and Conquer algorithm solves a problem using following three steps.
- Divide: Break the given problem into sub-problems of same type.
- Conquer: Recursively solve these sub-problems
- Combine: Appropriately combine the answers
Following are some standard algorithms that are Divide and Conquer algorithms. 1) Binary search, 2) Quick Sort, 3) Merge Sort, 4) Strassen’s Algorithm
Imagine P is a problem with size of n and S is the solution. In this case, if P is large enough to be divided into sub problem, for example P1, P2, P3, P4, ... , Pk; let say k sub problems and also there would be k solutions for each of k sub problems, like S1, 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 if P is sort then the P1, P2 and Pn must be sort too. So this is how it is recursive in nature. So, divide and conqure will be recursive.
Related