Divide-and-conquer algorithms

Divide and Conquer is an algorithmic paradigm in which the problem is solved using the Divide, Conquer, and Combine strategy.

A typical Divide and Conquer algorithm solves a problem using following three steps:

Divide: This involves dividing the problem into smaller sub-problems.
Conquer: Solve sub-problems by calling recursively until solved.
Combine: Combine the sub-problems to get the final solution of the whole problem.

A classic example of Divide and Conquer is Merge Sort demonstrated below. In Merge Sort, we divide array into two halves, sort the two halves recursively, and then merge the sorted halves.

Example: In this example, we will show the merge sorting using recursion:

Javascript

// JavaScript program for Merge Sort 
  
// Merges two subarrays of arr[]. 
// First subarray is arr[l..m] 
// Second subarray is arr[m+1..r] 
function merge(arr, l, m, r) { 
    let n1 = m - l + 1; 
    let n2 = r - m; 
  
    // Create temp arrays 
    let L = new Array(n1); 
    let R = new Array(n2); 
  
    // Copy data to temp arrays L[] and R[] 
    for (let i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (let j = 0; j < n2; j++) 
        R[j] = arr[m + 1 + j]; 
  
    // Merge the temp arrays back into arr[l..r] 
  
    // Initial index of first subarray 
    let i = 0; 
  
    // Initial index of second subarray 
    let j = 0; 
  
    // Initial index of merged subarray 
    let k = l; 
  
    while (i < n1 && j < n2) { 
        if (L[i] <= R[j]) { 
            arr[k] = L[i]; 
            i++; 
        } 
        else { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    // Copy the remaining elements of 
    // L[], if there are any 
    while (i < n1) { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    // Copy the remaining elements of 
    // R[], if there are any 
    while (j < n2) { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
// l is for left index and r is 
// right index of the sub-array 
// of arr to be sorted 
function mergeSort(arr, l, r) { 
    if (l >= r) { 
        return; 
    } 
    let m = l + parseInt((r - l) / 2); 
    mergeSort(arr, l, m); 
    mergeSort(arr, m + 1, r); 
    merge(arr, l, m, r); 
} 
  
// Function to print an array 
function printArray(A, size) { 
    for (let i = 0; i < size; i++) 
        console.log(A[i] + " "); 
} 
  
  
let arr = [3,9,6,4,5,7]; 
let arr_size = arr.length; 
  
mergeSort(arr, 0, arr_size - 1); 
  
console.log("Sorted array is "); 
printArray(arr, arr_size); 
  
// This code is contributed by SoumikMondal

Output

Sorted array is 
3 
4 
5 
6 
7 
9

Applications of Recursion in JavaScript

Recursion is a programming technique in which a function calls itself directly or indirectly. Using a recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc. Recursion is a technique in which we reduce the length of code and make it easy to read and write. A recursive function solves a problem by calling its own function and also calling for the smaller subproblem.

Recursion is a powerful technique that has many applications in the field of programming. Below are a few common applications of recursion that we frequently use:

Tree and graph traversal
Sorting algorithms
Divide-and-conquer algorithms
Sieve of Eratosthenes
Fibonacci Numbers

Let’s deep dive into each application:

Tags:

#JavaScript-DSA #JavaScript-Program #JavaScript #Web Technologies

Sorting algorithm

Sieve of Eratosthenes

Divide-and-conquer algorithms

Javascript

Applications of Recursion in JavaScript

Similar Reads

Contact Us