Divide & Conquer (Grokking Algorithms)

In this article we will use 2 Examples to explain the concept of Divide & Conquer.

The First Example will be a visual one and the latter one will be a code one.

EXAMPLE 1

Suppose you are a farmer with a plot of land. You want to divide this farms evenly into square plots. You want the plots to be as big as possible.

The following Constraints are present:-

Here to solve the farmer's problem, we will use Divide & Conquer Strategy!

The Divide & Conquer Strategy consists of two cases:-

1. Base Case : The simplest possible case!

2. Recursive Case : Divid eor decrease your problem until it becomes the Base Case.

Now solving the Farmer's problem:

• Let's start by marking out the bigest boxes you can use.

You can fit two 640x640 boxes in there and some land is still left to be divided!

• Now, apply the same algorithm to the remaining land!

The biggest box we can create is 400 x 400 m with 400 x 240 remaining area.

• Now mark a box to get an even smaller segment.

• Going for an even smaller box!

• Hey Look! we encountered the Base Case !

• So for the original farm, the biggest plot size you can use is 80 x 80 m.

EXAMPLE 2

You are given an array of numbers. You have to add all the numbers and return the total.

It's pretty easy to do it with a loop:

def sum(arr):
 total = 0
 for x in arr:
  total += x
 return total

But the challenge is to do it using Recursion!

Follow these steps to solve the problem:-

1 ) Figure out the Base Case

Think about the simplest case. Here, if we get an array with 0 or 1 element then thats pretty easy to sum up.

2 ) We need to move more closer to an empty array wit hevery recursive call.

3 ) Now the Sum Function Works :-

• It's Principal :

• Sum Function in Action and Recursion taking place :

Tip: When we are writing a recursive function involving an array, the base case is often an empty array with one element.