What is Recursion?

  • Definition: solving a problem by breaking it down into smaller instances of the exact same problem
  • Divides problem into smaller pieces and calls itself for each piece
  • Each Recursive Method has a base case and recursive method
    • Base case: condition that terminates the problem, the last time the function is called
    • Recursive case is each time the function is called with a smaller version of the problem

Recursion vs Iteration

  • Recursion is easier to read
  • Trade Offs:
    • Speed and memory
    • Recursion requires a call stack
  • Call stack: keeps track of all previous function calls
    • results of recursive calls are needed

Hacks

  • Binary Search repeatedly divides the list in two
  • must be presorted

Binary Search Iteration 

public int binarySearch(int[] array, int target) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
  int mid = (low + high) / 2;
  if (array[mid] == target) {
    return mid;
  } else if (target < array[mid]) {
    high = mid - 1;
  } else {
    low = mid + 1;
  }
}
return -1;
}

Binary Search Recursion 

public int binarySearch(int[] array, int target, int low, int high) {
    if (low > high) {
      return -1;
    }
    int mid = (low + high) / 2;
    if (array[mid] == target) {
      return mid;
    } else if (target < array[mid]) {
      return binarySearch(array, target, low, mid - 1);
    } else {
      return binarySearch(array, target, mid + 1, high);
    }
  }