# JavaScript Recursion with examples

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
```

### Q.2 Print numbers from 1 to n.

the first way to do this…

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

Output:

```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.