Recursion Examples in Javascript
Tags: javascript, react, html
Published: 2021-08-30 04:57:11

Hello Everyone Today we are going to see some simple Recursion Examples in Javascript to understand how recursion works.

What is Recursion?
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily.

Lets see Some examples of Recursion

Example 1 - Sum of Digits

```javascript
function sum_of_digit(n)
{
    if (n == 0)
    return 0;
    return (n % 10 + sum_of_digit(parseInt(n / 10)));
}

var num = 113;
var result1 = sum_of_digit(num);
console.log(result1);
```
```
Output - 
5
```

Working -

if n === 0 means number is 0 and we will return it as 0

Logic:
1. 113 % 10
Q = 11 and R = 3
2. 11%10
Q = 1 and R  = 1
3. 1%10
Q = 0 and R = 1

3+1+1 = 5

Example2 - Power
```javascript
function power(base,exp){
  if(exp === 0 ){
    return 1
  }
  else if(exp === 1){
    return base
  }
  else{
    return base*power(base,exp - 1);
  }
}

var result2 = power(2,5);
console.log(result2);
```
```
output - 
32
```

Working - 

if exponent is 0 it means the power is 0 and we return 1

if exponent is 1 it means the power is 1 so we will return the base as it is

Logic:
power(2,5)

1. 2*(2,5-1) = 4
2. 2*(2,4-1) = 3
3. 2*(2,3-1) = 2
4. 2*(2,2-1) = 1
5. 2*(2,1-1) = 0 so return 1

so it becomes 2*4 times 2 or 2*2*2*2*2 = 32


Example3 - GCD(Greatest Common Divider)

```javascript
function GCD(num1,num2){
  if(num1 < 0){
    num1 = -1 * num1;
  }
  else if(num2 < 0){
    num2 = -1 * num2
  }
  else if(num2 === 0){
    return num1
  }
  else{
    return GCD(num2 , num1%num2)
  }
}

var result3 = GCD(48,18);
console.log(result3);
```
```
output- 
6
```

Working - 

if number1 is negative then we  multiply it by -1 to make it postive and same
for number 2 

if number2 is 0 then we will return number1 as it is

Logic:
GCD(48,18)

Eculids theorem - 
48/18 = Q-2 and R=12
18/12 = Q=1 and R=6
12/6 = Q=2 and R=0 when R is zero we have to stop here and our answer is 6

GCD(48,18)
Then GCD(18,48%18) = GCD(18,12) = GCD(12,6) = GCD(6,0)
in last GCD function call number2 is 0 so we return number1 which is 6

Example4 - DecimalToBinary
```javascript
function decimalTobinary(num){
  if(num === 0){
    return 0;
  }
  else{
    return (num%2 + 10*decimalTobinary(parseInt(num/2)));
  }
}

var result4 = decimalTobinary(15);
console.log(result4);
```
```output
1111
```

Working - 

if number is 0 we return 0

Logic:

15

15%2 = Q-7 and R-1
7%2 = Q-3 and R-1
3%2 = Q-1 and R=1
1%2 = Q-0 and R=1 

Taking All R together - 1111 which is the binary equivalent of 15

Example5 - Factorial 

```javascript
function factorial(num){
  try {
    if(num === 1){
    return num
  }
  else{
    return num * factorial(num - 1);
  }
  } catch (e) {console.log("not a number!!")}
  
}

console.log(factorial(20))
```
```
output - 
2432902008176640000
```

Working - 

if number is 1 the factorial is 1

Logic - 
number = 4

num * factorial(num - 1) means
4 * (4-1) * (3-1) * (2-1) * 1 = 4*3*2*1 = 24


Example6 - Fibonacci
```javascript
function Fibonacci(num) {
  try {
    if(num in [0,1])
    {
      return num;
    }
    else{
      return Fibonacci(num-1) + Fibonacci(num-2);
    }
  } catch (e) {console.log("not a number")}
}

for(let i=0;i<5;i++){
console.log(Fibonacci(i));
}
```
```
output - 
0
1
1
2
3

```

Working - 
1![1_LNBBacuaBFOVZXUV6VgEEg](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ayzhrqo8m1yscl701un7.png)

Basically our fib function will continue to recursively call itself creating more and more branches of the tree until it hits the base case, from which it will start summing up each branch’s return values bottom up, until it finally sums them all up 


These are some of the Recursion Examples and there are many more to learn. So ,  keep Going and learn as much as you can.

I am learning DSA and trying to understand the concepts as much as i can , still if there is any mistake in this post , please mention it in the comment Section.

THANK YOU FOR READING THIS POST.

Instagram - https://instagram.com/w_a_a_d_u__h_e_c_k