Shubham Tiwari

Posted on Aug 30, 2021

Recursion Examples in Javascript

#javascript #react #html

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



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:

113 % 10 Q = 11 and R = 3
11%10 Q = 1 and R = 1
1%10 Q = 0 and R = 1

3+1+1 = 5

Example2 - Power



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)

2*(2,5-1) = 4
2*(2,4-1) = 3
2*(2,3-1) = 2
2*(2,2-1) = 1
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)



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



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

var result4 = decimalTobinary(15);
console.log(result4);

Working -

if number is 0 we return 0

Logic:

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



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



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

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