What are the Divide and Conquer algorithms?
Divide and conquer is where you divide a massive problem up into much smaller, much more comfortable to solve problems.
But how does it work? And why are we trying this approach? Solving a smaller problem is more natural than solving a big one. So divide and conquer algorithm tries to break a problem down into as many little easily manageable chunks as possible since it is easier to solve with small pieces. It does this with recursion.
Merge Sort Algorithm using Divide and Conquer
To implement a divide and conquer algorithm, we first must understand what Recursion is and how to use it? Recursion is a topic which gets hard to understand, but its a significant one. Now to understand recursion lets take the example of a Russian doll.
Now if you see them at first glance, it seems that there is a single doll. But if you open this one. There is a slightly smaller one inside. If you take this new one and open it, there is a somewhat smaller doll than this one, and this continues, you keep opening the doll, and a new smaller Russian doll comes from inside. This process ends when you find a doll which does not open. Its the smallest one and problem now has a terminating point. So you get many different Russian dolls from the initial one.
What do Russian dolls have to do with algorithms? Just as one Russian doll has within it a smaller Russian doll, which has an even smaller Russian doll within it, all the way down to a tiny Russian doll that is too small to contain another, we’ll see how to design an algorithm to solve a problem by solving a smaller instance of the same problem, unless the problem is so small that we can just solve it directly.
- Each recursive call should be on a smaller instance of the same problem.
- The recursive calls must eventually reach a base case, which can be solved directly.
Recursion is an excellent approach for specific problems, and many algorithms lend themselves to recursive solutions. However, recursive algorithms can be inefficient in terms of both time and space.
If you really want to understand recursion, then tower of Hanoi is a great example for understanding recursion. Khan Academy has a great resource for understanding the problem at this link.