What is Recursion in Programming

Recursion is calling a function itself multiple times to solve a given problem. Just like loops, you also need to specify when that function should stop calling itself. Such a condition is called as the base condition. 

For example, consider the below code which prints "Hello World" repeatedly. The showMessage function calls itself multiple times but the base condition is not defined and hence, this leads to an infinite loop.

function showMessage(n) {
    console.log("Hello world ", n);
    showMessage(n - 1);
}

showMessage(10);

Now, observe the code after adding the base condition. When n becomes 0, the recursive call stops.

function showMessage(n){
    if(n==0){
        return;
    }
    console.log("Hello world ",n);
    showMessage(n-1);
}

showMessage(10);

Let us see how to use recursion to perform some calculations. The below code calculates the sum of first n numbers.

function sum(n){
    if(n==1){
        return 1
    }
    else{
        return n+sum(n-1);
    }
}

var sumResult=sum(10);
console.log(sumResult);

Every recursion can be replaced with an equivalent iteration statement. Recursive algorithms are usually slower than iterative algorithms. In the above example which calculates the sum of first n numbers. Here, the sum of first 10 numbers is checked. If you want the sum of first 600000 numbers, the recursive code will crash. Interestingly, the below iterative algorithm to calculate the sum of n numbers has the same complexity, O(n).

function sum(n){
    var sum=0;
    while(n!=0){
        sum+=n;
        n--;
    }
    return sum;
}

var sumResult=sum(600000);
console.log(sumResult);

But the below equivalent code has a time complexity of O(1).

function sum(n){
    return n*(n+1)/2;
}

However, recursive algorithms have below advantages: 

• Recursion adds clarity and sometimes reduces the time needed to write and debug code. 
• Performs better in solving problems based on tree structures.