divide and conquer and recursion

recursion divide-and-conquer
Tim picture Tim · Feb 12, 2010 · Viewed 10.8k times · Source

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!

Answer

danben picture danben · Feb 12, 2010

"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.

Related questions

Divide and conquer algorithm for sum of integer array

I'm having a bit of trouble with divide and conquer algorithms and was looking for some help. I am attempting to write a function called sumArray that computes the sum of an array of integers. This function must be done …

Read More
Understanding double recursion

I'm able to comprehend recursion easily if there is just one recursive call within a function. However, I am really getting confused when I see two or more recursive calls within the same function. Example: int MaximumElement(int array[], int …

Read More
Maximum Subarray: Divide and Conquer

Disclaimer: this is for an assignment. I am not asking for explicit code, only enough help to understand the algorithm involved so that I might fix the errors in my code. Okay, so you're probably familiar with the maximum subarray …

Read More