JavaScript Recursion with examples

By Anil Kumar Sharma

Today’s topic is recursion, the question that arises here is,

What do you mean by recursion?

Recursion means recurring (occurring again and again or repetition), function calling itself.

Basically, the concept of recursion is based on PMI (Principle of Mathematical Induction) which we studied in high school. As we know in PMI we have a given equation and we have to prove for smaller value
i.e n=1. And we are assuming the Eqn. is correct for ‘ k ‘ and need to check for ‘ k+1 ‘.
In recursion, the concept is the same: base condition, function call, and small calculation.

Syntax:

function recur() {
    // base condition
    if(){
      //condition
    }
    // function calling itself
    recur();
    // ...
}

you can do a small calculation part before(during stack push-Tail recursion) or after repetitively calling the function(during stack pop). But the base condition should be above the function call. Suppose if we forget to put the base condition, it will form an infinite loop or program crash.

Q.1 Print numbers from n to 1.

function print(n){
  // base condition
  if(n==0){
    return ;
  }
  // small work
  console.log(n);
  //function call
  print(n-1);
}
print(5);

Output:

5
4
3
2
1

function print(n){
  // base condition
  if(n==0){
    return ;
  }
  //function call
  print(n-1);
  // small work
  console.log(n);
}
print(5);

1
2
3
4
5

the second way to do…

function print(n,i){
  // base condition
  if(n==0){
    return ;
  }
  // small work
  console.log(i);
  //function call
  print(n-1,i+1);
}
print(5,1);

Output:

1
2
3
4
5

Time complexity: O(n)

Space complexity: O(n)[internally stack is working to store functions]

Multiple recursion

Q. Print Fibonacci series using recursion in JavaScript

function fibo(num){
  if(num==0 || num==1){
   return num; 
  }
  return fibo(num-1)+fibo(num-2);
}
console.log(fibo(5));

Output:

5

Q. You have given a matrix n*m. find all possible paths to reach the destination in JavaScript. You have given the value of n and m.

Here, ‘h’ is the horizontal move and ‘v’ is the vertical move.

function printMazePaths(sr , sc , dr , dc , psf) {
          if(sr==dr && sc==dc){
             console.log(psf);
              return ;
          }
          if(sc<=dc){
              printMazePaths(sr, sc+1, dr, dc, psf+'h');
          }
           if(sr<=dr){
              printMazePaths(sr+1, sc, dr, dc, psf+'v');
          }
  }
let n=3,m=3; //n is the total no. of rows and m is the total number of columms.
printMazePaths(0, 0, n-1, m-1, "");

Output:

hhvv
hvhv
hvvh
vhhv
vhvh
vvhh

Recursion is very important for further topics like Backtracking, DP, Tree, and Graphs.