Day 3 --> Recursion

Hello! I'm back with one more new interesting topic.

Previously, we completed Time & Space Complexity which helped us increase our understanding of how time and space work in our program. I hope everyone learned and enjoyed my blog.

Now, starting with our new topic i.e. Recursion. Many of you might already be cleared with the concept of functions or methods. So to explain recursion in simple words, I can say that it's a block of code that calls itself repeatedly until terminated. Any operation that we perform with the help of a for loop can also be performed with the help of recursion.

Similarities between for loop and recursion: -

• Base Condition = Similarly like in a for loop we have a terminating condition, here we call it a base condition that terminates the recursive operation. In the absence of a base condition, the recursive call (a function call to itself is called a recursive call) will be continued till infinity.

• Recursive Relation = Like we perform some operations inside a for loop, similarly we perform operations inside a recursive function that is performed until or unless the base condition is met.

Example: - Factorial of Number: -

5! = 5x4x3x2x1 = 120

• Processing = The way recursion works is called processing. Firstly the recursive function is called from the main function and then the recursive function iterates until the base condition is acquired and afterwards it exists.

We have two types of recursion cases: - Tailed Recursion and Head Recursion.

• Tailed Recursion = As the name may suggest, in this type of recursion function, the recursive call is the last statement of the function. The example mentioned below is the type of tailed recursion: -

void recur(int n){
     if(n == 0){
            return;
     }
     else{
          recur(n-1);
     }
}

• Head Recursion = In the type of recursion, the recursive call is the first statement of the function. And to calculate the time complexity of these types of recursion cases, we would need to go through the concept of Recursion Backtracking. Example: -

•     void recur(int n){
           if(n == 0){
                  return;
           }
           recur(n-1);
      }