Recursion..(The Problem Solver)

#datastructure #recursion #computerscience #competetiveprogramming

The Regular Definition of recursion is "The Function called itself is Recursion." But Recursion is actually technique provides a way to break Bigger or Complex problems down into simpler problems which are easier to solve".
Before Going to Coding Part We are going to understand what recursion is,
To illustrate this thought process, let’s look at an example.

Just think of adding numbers 5 to 1
Now the simple way is, we just go from 1 to 5 one by one and add them
5+4+3+2+1 = 55

Now Imagine that there is magical box that will give you the result for sum of numbers from 4 to 1 , Now your work is to add just 5 to the result and you get your required solution.

What we are trying to do is , we just solve the bigger problem by breaking down into a problem that is one step simpler.

The magic box is nothing but the function that will give result for one step smaller problem.

Now you wonder that how this magic box will do my work, but the interesting part of recursion technique is to, Assume that my function will work to solve the simpler problem — really believe it beyond any doubt.

Now the Problem is After getting the result from that magic box what we do to get our complex problem result.........

We add 5 to result of magic box
5 + MagicBox(4)

This addition is what we called (Self Work)
We do some Self work that will going to merge with Simpler Problem solution and give me the required result.

Just Put All Above ingredients into the container you will get your required recursive dish .

Basically our ingredients are:

Identify the Bigger or Complex problem.

Break the problem into one step smaller problem.

Do self work to get the result

Now we are going to jump to the coding stuff,
Just Take up the above analogy in your hand....to think how recursive approach works
I won't be surprised if you're wondering why we gonna using recursion to calculate the sum of numbers from 5 to 1 ,Wouldn’t it be easier to write a loop?
However, it’s important for us to look at a straightforward example first, before we tackle any algorithms that really require recursion.

Step 1 : What is our Bigger Problem calculate the sum from 5 to 1

Step 2 : one step simpler problem is sum from 4 to 1
That is if N is our bigger problem then our smaller problem is (N-1)

5->4 ................N->(N-1)

Step 3 : ADD them to get the result

5 + MagicBox(4)
N + MagicBox(N-1)

main(){
int n = 5;
int result = sum(5);
}
function sum(int n){

 MagicBox = function sum(n-1);  // One Step Simpler Problem

 OurAnswer = n + MagicBox;  //SelfWork

}

This will work fine ..........

But the problem is if our MagicBox will run infinite time when we get our result.
Now here we get our next and most important ingredients called Base Case
Base Case is Nothing but our Endpoint where our Magicbox is going to Stop

For example : Our base case for above problem is if our N is less then or equal to 1 it will give the sum equals 1..

if(N<=1)
return 1;

main(){
int n = 5;
int result = sum(5);
}
function sum(int n){

  if(n<=1)           //Base Case
     return 1;

 MagicBox = function sum(n-1);  // One Step Simpler Problem

 OurAnswer = n + MagicBox;  //SelfWork

}

Just Put Again one more ingredients into the container.

Now our ingredients are:

Identify the Bigger or Complex problem. Then, let’s get the base case out of the way

Break the problem into one step smaller problem.

Do self work to get the result

Some people Think about how to break the problem down all the way to the base case. I thought this is not the right way to write recursion algorithms ,In order to develop the Recursion Algorithm, we should not think about how we could break the problem down all the way to the base case. That is the function’s job, not yours. Instead, we should only think for the problem that is one step simpler than the problem I am really trying to solve, and then I wrote our self work to solve the real problem.

Stay tuned for Part 2, Where we’ll explore About Stack and Heap will play there role in recursion and we will some more problems on recursion.