DEV Community

Bhav Kushwaha
Bhav Kushwaha

Posted on

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.


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.

1680 m x 640 m Farmland

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.



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
Enter fullscreen mode Exit fullscreen mode

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.

base case

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

recursive case 1

recursive case 2

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.

Top comments (0)