Understanding Recursion in JavaScript with a binary search example
Published: 2022-03-16 14:24:45

> 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. :)