Recursion Examples in Javascript

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:

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

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)

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);

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

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