divide and conquer and recursion

Question

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 1

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

Answer 2

A Divide-and-conquer algorithm is by definition one that can be solved by recursion. So the answer is yes.

Answer 3

Usually, yes! Merge sort is an example of the same. Here is an animated version of the same.