Divide and Coquer Algorithms

I have seen a lots of students feel it is difficult to develop Divide and Conquer Algorithms. It’s my pleasure if this document can help those students to have a proper understand of Developing Divide and Conquer algorithms. Let’s move onto the topic. In this discussion we will take Factorial as an instance.

1. You have to see that there exists smaller version of same type of problem(s). Solving these smaller versions should be easy than the original one. Further Results of these smaller versions should lead us to solve the original problem.
   Let’s think we have to find factorial of 6. Here we can see that if we know factorial 5 we can multiply it by 6 and find factorial 6. Actually it is easy to solve factorial 5 than factorial 6. 
2. Another thing you have to understand is base case. You must know the result of the base case.
   Base case of our example is we know factorial 1 equals to 1. 
3.  Here we are going to learn a very important point. That is you should have self confidence that the function you’re going to write, gives the correct answer.

Accordingly we can develop our function to calculate factorial of ‘n’.

 int factorial(int n){
/*since we know the result of the base case, 
we check input whether it is base case*/
     if(n == 1){

//Yes it is base case. Now we can return our known value
          return 1;
     }
     else{
/*Oops. It is not the base case. We don’t know the answer.
But if we know factorial n-1, we can find factorial n. Let’s 
move in that direction using our same function since we 
believe it returns the correct value*/
          return factorial(n-1)*n;
    }
}

Let's think in a different way.

All the students knows the answer to factorial 1. But no one knows the answers for higher numbers.

If someone ask me the answer for factorial 3, I will ask Mr. A to find the answer of factorial 2. Until he send me the answer I have to terminate my calculation.

Since he don't know the answer for factorial 2, he will ask Mr. B to find factorial 1.

Awesome. Mr. B knows the answer. He will send answer as 1. Then Mr. A can calculate his answer 1 x 2 = 2. Then I will recieve the answer for factorial 2 from Mr. A.

Now I can find factorial 3. That is 2 x 3 = 6.

That's how it works. I think you will benefit of this document. If you have any doubts feel free to contact me.