Algorithms using Recursion in Javascript

Divide and Conquer Algorithms:

Divide and Conquer is one of the algorithm paradigms that uses recursion.

Here,

• The large problem is divided into smaller problems - Divide.

• These smaller problems are of the same type.

• These smaller problems are solved recursively - Recursion.

• The results of smaller problems are combined to get the final solution - Conquer.

Dividing the array until it reaches the single value:

Take an array and divide it into half until it reaches a single value.

Getting a single value will be the base case.

Dividing the array will be a recursive case.

We will look into example,

function Divide(arr) {
    // evaluate the length of array
        let arrLength = arr.length
    // Base case
    // Ifarray length is one
    if(arrLength === 1 || arrLength === 1){
        return arr
    } 
    
    // Recursive case  
    // If array length greater than 1
    // Divide the array
    if(arrLength > 1) {
    
    // Divide the array in to half
    // Array length can be odd or even number
    // If odd --> Math.ceil will give nearest greater integer
    // e.g.Math.ceil(6.5) is 7
    
        let midIndex = Math.ceil(arrLength / 2)
    
    // We have two arrays
    // Slice(start,end) --> start included and end excluded
    // To include end --> index + 1 = arrLength
    
      let leftArr = arr.slice(0,midIndex) // Takes only left half of array
      return Divide(leftArr)
    }
}

const array = [5,10,16,19,20,8,4]
Divide(array) // [5]

The call stack would be,

Similarly, for the right half of the array,

function Divide(arr) {
    // evaluate the length of array
        let arrLength = arr.length
    // Base case
    // Ifarray length is one
    if(arrLength === 1 || arrLength === 1){
        return arr
    } 
    
    // Recursive case  
    // If array length greater than 1
    // Divide the array
    if(arrLength > 1) {
    
    // Divide the array in to half
    // Array length can be odd or even number
    // If odd --> Math.ceil will give nearest greater integer
    // e.g.Math.ceil(6.5) is 7
    
        let midIndex = Math.ceil(arrLength / 2)
    
    // We have two arrays
    // Slice(start,end) --> start included and end excluded
    // To include end --> index + 1 = arrLength
    
     // Takes only right half of array
     let rightArr = arr.slice(midIndex,arrLength)
     return Divide(rightArr)
    }
}

const array = [5,10,16,19,20,8,4]
Divide(array) // [4]

The call stack would be,

If we observe, we actually reach left most elements and rightmost elements of an array, respectively.

If we need to get the value , just give index of 0 because at last we have array of length 1.

Binary Search:

We can search elements in an array using binary search.

Condition is array should be sorted.

So we need to give a sorted array.

Same divide approach until we hit an array of length 1.

For example, if we want to find 10 in [5,10,15,20,25,30,35,40,45,50].

We don't have to loop through all the elements in the array(Note: Array should be sorted)

Binary search is all about finding mid index value and searching only in array-half that contains that number.

Let me show you,

function BinarySearch(arr,toFind,start,end) {

    // If start index is greater than end , it is empty array
    // Base case
    if(start > end) {
        return false
    }
    
    //Finding the mid index
    let mid = Math.ceil((start + end)/2)
    
    // Base case
    // If Midinde value = toFInd value --> Return true
    if(arr[mid] === toFind) return true
    
    // Recursive case
    if(arr[mid] > toFind) {
    // The element should be in left array
    // We give mid-1 because we already checked mid before
        return BinarySearch(arr,toFind,start,mid - 1)
    }
    else {
    // The element should be in right array
    // We give mid+1 because we already checked mid before
        return BinarySearch(arr,toFind,mid + 1,end)
    }
}

const arr = [5,10,15,20,25,30,35,40,45,50]
console.log(BinarySearch(arr,10,0,arr.length -1)) // true

The call stack would be,

If we want to find 55, then the call stack would be,