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:
Tree traversal
The traversal of trees is very interesting, we can traverse trees in different ways. Recursion is also a very common way to traverse and manipulate tree structures.
Example: In this example, we will show all three traversal(inorder, postorder and preorder) using recursion.
Javascript
// javascript program for different tree traversals // Class containing left and right child of current // node and key value class Node { constructor(val) { this.key = val; this.left = null; this.right = null; } } // Root of Binary Tree let root = null; // In-Order Traversal: Left -> Root -> Right function printInorder(node) { if (node == null) return; // First recur on left child */ printInorder(node.left); // Then print the data of node console.log(node.key); // Now recur on right child printInorder(node.right); } // Pre-Order Traversal: Root -> Left -> Right function printPreorder(node) { if (node == null) return; // First print the data of node console.log(node.key); // then recur on left child */ printPreorder(node.left); // Now recur on right child printPreorder(node.right); } // Post-Order Traversal: Left -> Right -> Root function printPostorder(node) { if (node == null) return; // then recur on left child */ printPostorder(node.left); // Now recur on right child printPostorder(node.right); // First print the data of node console.log(node.key); } // Driver method root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); console.log("Inorder traversal of binary tree is "); printInorder(root); console.log("Preorder traversal of binary tree is "); printPreorder(root); console.log("Postorder traversal of binary tree is "); printPostorder(root); |
Inorder traversal of binary tree is 4 2 5 1 3 Preorder traversal of binary tree is 1 2 4 5 3 Postorder traversal of binary tree is 4 5 2 3 1
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
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 |
Sorted array is 3 4 5 6 7 9
Sieve of Eratosthenes
This algorithm is most optimised solution for finding the prime number.
Example: In this example, we will show the Sieve of Eratosthenes.
Javascript
function sieveOfEratosthenes(num) { const primeNum = new Array(num + 1).fill(true); primeNum[0] = primeNum[1] = false; for (let i = 2; i * i <= num; i++) { if (primeNum[i]) { for (let j = i * i; j <= num; j += i) { primeNum[j] = false; } } } return primeNum; } function isPrime(num) { if (num < 2) { return false; } const primes = sieveOfEratosthenes(num); return primes[num]; } // Test the function console.log(isPrime(97)); console.log(isPrime(66)); |
true false
Fibonacci Numbers
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation: F_{n} = F_{n-1} + F_{n-2} with seed values and F_0 = 0 and F_1 = 1 .
The Nth Fibonacci Number can be found using the recurrence relation shown above:
- if n = 0, then return 0.
- If n = 1, then it should return 1.
- For n > 1, it should return Fn-1 + Fn-2
Example: In this example, we will find the nth Fibonacci Number using Recursion.
Javascript
// Javascript program for Fibonacci Series // using Recursion function Fib(n) { if (n <= 1) { return n; } else { return Fib(n - 1) + Fib(n - 2); } } // driver code let n = 6; console.log(n + "th Fibonacci Number: " + Fib(n)); |
6th Fibonacci Number: 8
