Divide and Conquer: The recursive paradigm

5 min readMar 24, 2021

Divide and Conquer is a recursive algorithmic paradigm that divides a problem into smaller subproblems, solves the subproblems recursively, and then combines the subproblem solutions to solve the original problem. We will typically reduce the time complexity of a problem using this approach.

Major Steps

The three main steps in the divide and conquer paradigm are:

Divide:

Breaking the problem down into smaller sub-problems is the next step. Sub-problems can be a subset of the main problem. This move splits the problem in a recursive way until no further sub-problems can be separated.

Conquer:

This move is tasked with resolving a slew of smaller sub-problems. At this stage, problems are generally considered ‘solved’ on their own.

Combine:

As the smaller sub-problems are solved, this stage incorporates them in a circular manner before the initial problem is solved. This algorithmic solution is recursive, and the conquer and merge phases are so similar together that they seem to be one.

Let’s take a basic example to understand the approach. Let’s say we have 8 numbers:

2 3 5 1 4 7 9 8

And we’d like to add them all together. We divide the problem into eight sections, each containing a different set of numbers. So we add two numbers at a time, then four numbers into eight numbers to get our resultant.

2+3, 5+1, 4+7, 9+8

And so on.

A question arises here that why do we split it down to 8 individual numbers rather than stopping at pairs of numbers when we’ll just go back to that step?

Answer is simple in my opinion, what if we have a single input? Or an odd set of numbers? To cope with these cases, we need to break it down into singular numbers.

A divide and conquer algorithm attempts to split a problem down into as many small bits as possible, as small bits are simpler to solve. It usually accomplishes this by recursion.

How Recursion helps ?

Recursion means “defining a problem in terms of itself”. This can be a very powerful tool in writing algorithms. Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves.

For example, the Fibonacci sequence is defined as: F(i) = F(i-1) + F(i-2)

The base case and the recursive call are the two key components of a recursive function. The base case is critical since the function will logically loop indefinitely without it.

DnC based Algorithms

The following computer algorithms are based on divide-and-conquer programming approach −

Merge Sort
Quick Sort
Binary Search
Strassen’s Matrix Multiplication
Closest pair (points)

Merge Sort

Merge sort is a sorting algorithm. The algorithm roughly works as follows:

Divide the sequence of n numbers into 2 halves
Recursively sort the two halves
Merge the two sorted halves into a single sorted sequence

In the example above, we used merge sort to construct a sorted array from an unsorted array. Let’s take a closer look at each move to see how the algorithm works.

1. First, we looked at the Hello[10, 3, 7, 1, 15, 14, 9, 22] list. There are a total of 8 elements in this array.

2. As we saw earlier merge sort uses the divide and conquer approach to sort the elements. We found m which lies in the middle of our array and divided our array from the middle where m = (a — n)/2 ‘a’ is the index of the leftmost element and n is the index of the rightmost element of our array.

3. After the first division, we have 2 parts consisting of 4 elements each. Let’s look at the first half [10, 3, 7, 1].

4. We divide [10, 3, 7, 1] in 2 parts [10, 3] and [7, 1]. After that we divide them further into [10], [3], [7], [1]. Further division is not possible as we can’t calculate m. a list containing a single element is always considered sorted.

5. How does merging take place? Let’s find out. First [10] and [3] is compared and merged in ascending order [3, 10] in the same way we get [1, 7]

6. After that, we compare [3, 10] and [1, 7]. Once compared we merge them in ascending order and We get [1, 3, 7, 10].

7. [15, 14, 9, 2] is also divided and combined in a similar way to form [9, 14, 15, 22].

8. In the last step we compare and combine [15, 14, 9, 2] [9, 14, 15, 22] to give us our sorted array i.e. [1, 3, 7, 9, 10, 14, 15, 22].

Quick Sort

The quicksort algorithm is a sorting algorithm that sorts an array by choosing a pivot element, and partition the array around the pivot such that elements smaller than the pivot are moved to the left of pivot, and elements larger than the pivot are moved to the right of pivot.

Here is how a quick sort algorithm works for a given array of 6 elements.

Binary Search

Binary search is the most popular Search algorithm. It is efficient and also one of the most commonly used techniques that is used to solve problems.

If all the names in the world are written down together in order and you want to search for the position of a specific name, binary search will accomplish this in a maximum of 35 iterations.

Binary search works only on a sorted set of elements. To use binary search on a collection, the collection must first be sorted.

When binary search is used to perform operations on a sorted set, the number of iterations can always be reduced on the basis of the value that is being searched.