Divide and conquer is a problem solving technique that utilizes recursion to solve a problem by "dividing" the problem into smaller and smaller sub-problems. The base case of the recursion solves the group of the smallest sub-problems. The "conquer" portion of this problem solving technique then combines these solutions to create the solution to the original problem.
Figure 1 Dividing a problem
Generally, divide and conquer algorithms utilize two recursive function calls. Having two recursive calls continually divides the problem space into two parts. Figure 1 illustrates a typical "divide" step that uses two recursive calls. When the recursion reaches the base case, the sub-problems are solved directly. The solutions to these sub-problems are then combined together (as the recursion unwinds) and eventually form the solution to the original problem. Figure 2 shows the solved sub-problems combined into a solution for the original problem.
Figure 2 The combined solution
Consider the problem of calculating the sum of the squares of a range of integers. We can apply the divide and conquer approach to reduce the range continually until we reach a sub-problem size that is easily calculated. Listing 1 contains the source code for this recursive, divide-and-conquer based algorithm.
| 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: | #include <iostream> #include <cstdlib> using namespace std; int ssq(int m, int n) { if (m == n) { return m * m; // base case } else { int middle = (m + n) / 2; // recursive divide return ssq(m, middle) + ssq(middle + 1, n); } } int main(int argc, char* argv[]) { cout << "ssq(1,10) = " << ssq(1, 10) << endl; return EXIT_SUCCESS; } |
| Listing 1Finding the sum of the squares of a range of integers |
Another example of a simple and effective divide and conquer based algorithm appears in Listing 2.
| 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: | #include <iostream> #include <cstdlib> using namespace std; int find_smallest(int a[], int size) { if (size == 1) { return a[0]; // base case } else { // Search the first half of the array for the smallest element. int s1 = find_smallest(a, size / 2); // Search the second half of the array for the smallest element. int s2 = find_smallest(a + size / 2, size - size / 2); return (s1 < s2) ? s1 : s2; } } int main(int argc, char* argv[]) { int arr[] = {13, 19, 12, 11, 15, 19, 23, 12, 13, 22, 18, 19, 14, 17, 23, 21}; cout << "smallest: " << find_smallest(arr, 16) << endl; return EXIT_SUCCESS; } |
| Listing 2Finding the smallest element in an array |
Function find_smallest determines the smallest element stored in an array by continually dividing the array into two smaller pieces. When these pieces are small enough that they only contain one element, the algorithm then compares the elements stored in two pieces and returns the smaller of the two elements.