Basics

  • Recursive method calls itself
  • Should have at least one case to stop recursion (uses local variables)
  • Similar to iteration, but sometimes more convenient
public static void test(int n) {
    if (n > 0) {
        test(n-1);
    }
}
  • Binary search continually splits array in two to reduce values to search for target
  • Must be sorted
  • Ex: if searching for 23 in array of even numbers, high and low boundaries will converge on 22 and 24
  • Program will know that 23 is not in array and stop recursion

Merge sort

  • Used to sort ArrayLists
  • Divides array in half, calls itself for two halves to sort and then merges the halves back into one array
  • Can copy array, go through each element to compare and return each element sorted in original