Beginning Java Data Structures and Algorithms

The Divide and Conquer Approach

In a divide and conquer approach, we solve a problem recursively, applying the following three steps at each level of recursion:

• Divide the problem into more than one subproblems that are smaller instances of the same problem.
• Conquer the subproblems by solving them recursively. Eventually, the subproblem sizes are small enough for them to be solved in a straightforward manner.
• Combine the solutions to the subproblems in the solution for the original problem.

When a subproblem is large enough to be solved recursively, we call that the recursive case. When a subproblem becomes small enough that recursion is no longer necessary, we say that we have reached to the base case. It is common to solve subproblems ...