Skip to main content

recursion in JavaScript

Video Course With Step By Step Explanation Available on Coding Step By STep Android App

coding step by step android app

Scan the above QR or click on this link

What is Recursion ?

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself.

What is a recursive function ?​

In computer science, a recursive function is a function that calls itself repeatedly to get the solution. Recursive functions solve complex problems through the “divide-and-conquer” method.

What is a Base Case or terminating case is recursive function ?​

Recursive function calls itself to get the solution. It will result an infinite loop resulting stack overflow, if we have not mentioned the terminating condition. This terminating conditionis known as terminating case or base case.

Stack overflow is when the maximum number of call stacks of the program exceeds the limited amount of address space.

Example Program using loop​

function printNumbers(n){
    for(let i=1; i<=n; i++){
    console.log(i);
  }
}

printNumbers(5)

Same Program using loop​

function printNumbers(n){
  if(n <= 0)
    return;
  printNumbers(n-1)
  console.log(n)
}

printNumbers(5)

The base case for this function is when n is smaller or equal to 0. This is because the desired outcome was to stop counting at 0. In addition to a base case, this recursive function also exhibits the divide-and-conquer method.

Divide-and-Conquer Method​

Divide-and-Conquer Method is the method where we divide the main problem in to smaller pieces and solve them.

Tail recursion​

If the recursive call occurs at the end of a method, it is called a tail recursion. The tail recursion is similar to a loop. The method executes all the statements before jumping into the next recursive call.

function printNumbers(n){
  if(n <= 0)
    return;
  console.log(n)
  printNumbers(n-1)
}

printNumbers(5) // 5 4 3 2 1

Head Recursion​

If the recursive call occurs at the beginning of a method, it is called a head recursion. The method saves the state before jumping into the next recursive call.

function printNumbers(n){
  if(n <= 0)
    return;
  printNumbers(n-1)
  console.log(n)
}

printNumbers(5) // 1 2 3 4 5

Fibonacci Sequence Example using loop​

function printFibo(number) {
  let n1 = 0, n2 = 1, nextTerm;
  for (let i = 1; i <= number; i++) {
      console.log(n1);
      nextTerm = n1 + n2;
      n1 = n2;
      n2 = nextTerm;
  }
}

printFibo(5)
function getNthFibo(n) {
  if (n <= 1) {
    return n;
  } else {
    return getNthFibo(n - 1) + getNthFibo(n - 2);
  }
}

function printFibo(number) {
  if(number < 0)
    return;
  printFibo(number-1)
  console.log(getNthFibo(number))
}

printFibo(5)

Explanation of getNthFibo​

=> getNthFibo(5) + getNthFibo(4)
=> getNthFibo(4) + getNthFibo(3)+getNthFibo(3) + getNthFibo(2)
=> getNthFibo(3) + getNthFibo(2)+getNthFibo(2) + getNthFibo(1)+getNthFibo(2) + getNthFibo(1)+getNthFibo(1) + 1
=> getNthFibo(2) + getNthFibo(1)+getNthFibo(1) + getNthFibo(0)+getNthFibo(1) + getNthFibo(0)+1+getNthFibo(1) + getNthFibo(0)+1+1+1
=> getNthFibo(1) + getNthFibo(0) + 1 + 1 + 0 + 1 + 0 +1+0+1+1+1
=> 1+0+1+1+0+1+0+1+0+1+1+1
=> 8
  • Time Complexity O(2^n)

Optimised solution​



function getNthFibo(n, lastlast, last) {
    if (n == 0)
    return lastlast;
    
    if (n == 1)
    return last;
    
    return getNthFibo(n-1, last, lastlast+last);
}

function printFibo(number) {
  if(number <= 0)
    return;
  printFibo(number-1)
  console.log(getNthFibo(number, 0, 1))
}

printFibo(8)
  • Time Complexity: O(n)

Because, This function executes maximum n times as it’s decremented by n-1 each time with only single recursive call.

Example Program : Pascal's triangle​

Pascal’s triangle is a triangle whose element value is the summation of its top two (left and right) values. In this example, We will explore a function to calculate a term of Pascal’s triangle. 

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
Base case: The base case for Pascal’s triangle is that when col is zero return 1 or when col is row number then return 1.Divide and conquer: By the mathematical definition of Pascal’s triangle, a term of Pascal’s triangle is defined as the sum of its upper terms. Therefore, this can be expressed as the following: pascalTriangle(row - 1, col) + pascalTriangle(row - 1, col - 1)

recursion program​

function pascalTriangle(row, col) {
  if (col == 0 || col == row) {
    return 1;
  } else {
    return pascalTriangle(row - 1, col) + pascalTriangle(row - 1, col - 1);
  }
}
console.log(pascalTriangle(0, 0)); // 1
console.log(pascalTriangle(1, 0)); // 1
console.log(pascalTriangle(1, 1)); // 1
console.log(pascalTriangle(2, 0)); // 1
console.log(pascalTriangle(2, 1)); // 2
console.log(pascalTriangle(2, 2)); // 1

Recursive Call Stack Memory​

When a recursive function calls itself, that takes up memory and time, and this is really important in Big-O space and time complexity analysis.

function printNumbers(n){
  if(n <= 0)
    return;
  console.log(n)
  printNumbers(n-1)
}

printNumbers(5) // 5 4 3 2 1

In the above example

  • Time complexity: O(n)
  • Space Complexity: O(n)

Recursive functions have an additional space complexity cost that comes from the recursive calls that need to be stored in the operating system’s memory stack. The stack is accumulated until the base case is solved. In fact, this is often why an iterative solution may be preferred over the recursive solution. In the worst case, if the base case is implemented incorrectly, the recursive function will cause the program to crash because of a stack overflow error that occurs when there are more than the allowed number of elements in the memory stack.