Recursion - A must-know algorithm.

Anyone who has learned a programming language would ideally learn about iterations using loops like for, while, do-while, and forEach, etc. We use these loops to achieve repetitive computations. Most common examples are computing the factorial of the given number, verifying if the string is a palindrome, computing the powers of a number, etc. There are many more real-time scenarios where you would get to use iterations. However, there is an interesting and efficient way of achieving similar results as of using an iteration loop.

The first time when I wanted to understand the difference between the two concepts and how they actually make a difference in terms of efficiency, I found a youtube video, where Anjana Vakil is explaining these concepts. I was so amazed at the way she explained the concepts that I can never ever forget that in my life. She compared these two concepts with two great Hollywood blockbuster movies. She mentioned that the iteration is more like "The ground hog's day", where a reporter lands in a new place for gathering news about a special day celebrated in that place and gets stuck in the same day for many days. He literally wakes up on the same day every single day, until he makes peace with it and finds true love. The second movie in which Anjana referred to the recursion similarity is "Inception", where people could dream inside a dream, inside a dream, and so on.

Let us pick a problem to understand the concepts better. The most common problem is computing the factorial of the given number. Find the below code for the iteration approach.

const factorial = (n) => {
    let result = 1;
    for(let i=n; i>1; i--) {
       result = result * i;
    }
    return result;
};

console.log("The factorial of ", 5 , " is ", factorial(5));

Here, we have used a for loop to achieve factorial of the given number n. We have initialized the result to 1, because we want to set the default value for the cases where n is not greater than to 1. You want to make sure the given number is positive for computing. Moving on to the loop, we are running the loop as long as the value of i(initialized to n) comes down to 1. We are decrementing the value of i after every iteration. Inside the loop, we are computing result as result multiplied by i value. So, the steps for an n=5 would be:

result = 1 * 5  //here i = n = 5, result was 1 and becomes 5 now
result = 5 * 4 //here i = 4, result becomes 20
result = 20 * 3 //here i = 3, result becomes 60
result = 60 * 2 //here i = 2, result becomes 120

As any number except 0, multiplied by 1 results in the same number, we have skipped that step by excluding it in the conditional part of the loop.

Let us move on to the interesting part of the blog. Find the below code for the recursion approach to the same problem.

const factorial = (n) => {
    if( n === 0){
       return 1
     } else {
       return n * factorial( n-1 )
     }
};

console.log("The factorial of ", 5 , " is ", factorial(5));

This is such a pleasure to code. We are calling the same factorial function by decrementing the argument by 1 each time until the given number comes down to 1. We have saved a good amount of memory space in this approach. We are actually dividing the problem into smaller subproblems until we reach a base case that is solved without undergoing any further recursion.

That means we are dividing the problem of 5! (5 factorial) into sub-problems as follows:

5! = 5 *4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!

That's all for now. I hope this was helpful. Thank for reading so far. Happy learning!!