Menu
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!
759
As mentioned above, we use recursion to implement the divide and conquer algorithm. A recursive algorithm calls itself with smaller or simpler input values. We call that the recursive case. So, when we implement the divide step we determine the recursive case which will divide the problem into smaller subproblems.
Divide and Conquer is a recursive problem-solving approach which break a problem into smaller subproblems, recursively solve the subproblems, and finally combines the solutions to the subproblems to solve the original problem. This method usually allows us to reduce the time complexity to a large extent.
Merge/Combine When the smaller sub-problems are solved, this stage recursively combines them until they formulate a solution of the original problem. This algorithmic approach works recursively and conquer & merge steps works so close that they appear as one.
The divide and conquer approach divides a problem into smaller subproblems; these subproblems are further solved recursively. The result of each subproblem is not stored for future reference, whereas, in a dynamic approach, the result of each subproblem is stored for future reference.
"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.
65
A Divide-and-conquer algorithm is by definition one that can be solved by recursion. So the answer is yes.
23
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
