Sorting algorithm
A Sorting Algorithm is used to rearrange a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure. There are various types of sorting. We are going to see insertion sort using recursion.Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
Example: In this example, we will see the insertion sort using recursion.
Javascript
// Recursive Javascript program for // insertion sort function insertionSortRecursive(arr, n) { // Base case if (n <= 1) return; // Sort first n-1 elements insertionSortRecursive(arr, n - 1); // Insert last element at its // correct position in sorted array. let last = arr[n - 1]; let j = n - 2; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > last) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = last; } // Driver Method let arr = [8,6,1,3,5,9]; insertionSortRecursive(arr, arr.length); for (let i = 0; i < arr.length; i++) { console.log(arr[i] + " "); } |
1 3 5 6 8 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:
Contact Us