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