Recursion

  • Recursive method calls itself
  • Base case: when the method stops calling itself
  • Recursive case: when the method calls itself
  • Has its own local variables, parameter values take progress of recursion
  • Can be used to traverse an array, arraylist, etc.

Example 

public static void example(int n) {
    if (n > 0)
        example (n-1);
}

Binary Search using Recursion

  • More efficient than linear search - which is when you go one by one in order.
  • Search for a target by seeing if it's higher or lower than the middle value
    • If it's higher, search the right half of the array
    • If it's lower, search the left half of the array
    • Can use recursion to do this for each iteration of the search

Merge Sort

  • Divides an array into halves, sorts each half, and then merges the two halves.
    • Can require taking half of a half to sort that part of the array.

Recursion Tree

  • Visualize recursive function calls, all possibilties

Homework

  • Completed google form quiz