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:-
Base Case : The simplest possible case!
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.
Top comments (0)