• A recursive method is a method that calls itself - a subproblem that calls itself repeatedly

Two parts to the method:

  • a base case
  • recursive call

After multiple calls, the base case is reached where recursion is stopped and a value is returned

Should be written first to avoid infinite recursion

//example of base case
int fact(int n)
{
    if (n < = 1) // base case
        return 1;
    else    
        return n*fact(n-1);    
}
  • Binary search algorithm
  • Data must be in sorted order
  • Keeps halving array until value is found
  • More efficient than linear search (O(log2n) vs O(n))

Big O notation

  • How long an algorithm takes to run
  • HashMap has O(1) which is same amount of time to execute
  • Binary Search has O(log N) which means it takes an additional step each time data doubles
  • Single and Nested loop is O(1)
// Java Program to Illustrate Recursive Binary Search
import java.util.*;
 
// Main class
class Binary {
    // Recursive binary search
    // Returns index of x if it is present
    // in arr[l..r], else return -1
    int binarySearch(int arr[], int l, int r, int x)
    {
        // Restrict the boundary of right index
        // and the left index to prevent
        // overflow of indices
        if (r >= l && l <= arr.length - 1) {
 
            int mid = l + (r - l) / 2;
 
            // If the element is present
            // at the middle itself
            if (arr[mid] == x)
                return mid;
 
            // If element is smaller than mid, then it can
            // only be present in left subarray
            if (arr[mid] > x)
                return binarySearch(arr, l, mid - 1, x);
 
            // Else the element can only be present
            // in right subarray
            return binarySearch(arr, mid + 1, r, x);
        }
 
        // We reach here when element is not present in
        // array
        return -1;
    }
  
    
}

Linear Recursion

A function that only makes a single call to itself each time the function runs (as opposed to one that would call itself multiple times during its execution)

  • Selection Sort: The algorithm works by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the end of the sorted part

  • Merge Sort: It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves