Understanding Recursion in JavaScript with a binary search example

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

In simple terms a recursion is technique of creating a function that calls itself until it does not.

All recursive function will have two cases:

• *base case *- which will not call itself
• *recursive case *- which calls its self

The best way to understand this is to do an example.

Let's say you have a sorted array of integers and want to check if a target number exists in that array or not. Since there are multiple ways to solve this problem. The most common one is to loop through the entire array to check if it is equal to the target number or not.

But in this article we will solve this using recursion which is more efficient in nature.

function isPresent(nums, target) {
  let middleIndex =  Math.floor(nums.length / 2);
  let middleElement = nums[middleIndex];

  // base case
  if (middleElement === target) return true;
  // recursive case
  else if (middleElement < target && nums.length > 1) {
    return isPresent(nums.slice(middleIndex, nums.length), target);
  }
  else if (middleElement > target && nums.length > 1) {
    return isPresent(nums.slice(0, middleIndex), target);
  }
 // in case if the value does not exists
  else return false;
}

isPresent([5, 7, 9, 11, 13, 19, 36, 39, 72], 19); // returns true

Here, isPresent() function is a recursive function which accepts two parameters nums - sorted array of integers and target - number that we wish to find.

Inside the function before the base case we will get the middle index of the array to find the middle element of the array.

Our base case will check if the middle element is equal to the target, then we will simply return true.

Now onto the recursive part the function. Here we will check for the two cases

• if the target is greater than the middle element - we will call the function again but with the new array which consists of all the numbers after the middle element.
• if the target is less than the middle element - we will call the function again but with the new array which consists of all the numbers before the middle element.

Understanding the recursive case:

isPresent([5, 7, 9, 11, 13, 19, 36, 39, 72], 19)

// the given array's middle element
let middleIndex = Math.floor(nums.length / 2);
let middleElement = nums[middleIndex];
console.log(middleElement); // 13

Since the current middle element 13 is **not equal **to the target number 19, our function will move to the recursive part.

return isPresent(nums.slice(middleElement, nums.length), target)
// this action will rerun the function and this time
console.log(middleElement) // will be 36

Now since the middle element 36 is not only not equal to the target number 19 but also less than the target

return isPresent(nums.slice(0, middleIndex), target);
// this action will also reurn the function and this time
console.log(middleElement) // will be 19

Finally our middle element is 19 which is equal to the target and fulfils the base case, the function will return true and the recursion will end.

Conclusion

In this article you learned what a recursion is and how to make use of recursion in JavaScript to check if a number exists in a given sorted array. If you enjoyed reading the article and it helped you learn something please do like and share it with others. :)