Recursion Part 2

More Recursion Examples

Recursive Binary Search

• Dichotomic divide-and-conquer search algorithm
• Search for item in ordered data set
• Can use key/value stores (order by key, each key corresponds to one value (i.e. phone book))
• Halves number of items each iteration of algorithm
• O(log₂ N)

Comparison with sequential sort

The chart below shows how many operations a binary search vs a sequential search performs based on the algorithm type.

Data Size / Sort Type	Binary Search	Sequential Search
10	3.3	10
100	6.6	100
10,000	13.3	10,000
1,000,000	19.9	1,000,000
1,000,000,000	29.9	1,000,000,000

A Recursive Sequential Search

public int sequentialSearch(int[] data, int item, int i) {
  // Searched entire array, but did not find item
  if(i == data.length) {
    return -1;
  }

  // Found the item
  if(data[i] == item) {
    return i;
  }
 
  // Keep searching
  return sequentialSearch(data, item, i + 1);
}

A Recursive Binary Search

Base Cases

• The item is not in the data
• The item has been found

Recursive cases

• Is the item we're looking for greater than the current middle?
• Is the item we're looking for less than the current middle?

// Public helper method
public int binarySearch(int[] data, int item) {
  return binarySearch(data, item, 0, data.length - 1);
}

// Private recursive method
private int binarySearch(int[] data, int item, int low, int high) {
  // Find the midpoint
  int middle = (low + high) / 2;
    
  // Item is not in data
  if(low > high) {
      return -1;
  }
    
  // Item matches middle
  if(data[middle] == item) {
      return middle;
  }
    
  // Item is less than curent middle
  if(item < data[middle]) {
      return binarySearch(data, item, low, middle - 1);
  }
  // Item is greater than current middle
  else {
      return binarySearch(data, item, middle + 1, high);
  }
}

Generic Binary Search

// Public helper method
public <T extends Comparable<T>> int binarySearch(T[] data, T item) {
  return binarySearch(data, item, 0, data.length - 1);
}

// Private recursive method
private <T extends Comparable<T>> int binarySearch(T[] data, T item, int low, int high) {
  // Find the midpoint
  int middle = (low + high) / 2;
    
  // Item is not in data
  if(low > high) {
      return -1;
  }
    
  // Item matches middle
  if(data[middle].compareTo(item) == 0) {
      return middle;
  }
    
  // Item is less than curent middle
  if(item.compareTo(data[middle]) < 0) {
      return binarySearch(data, item, low, middle - 1);
  }
  // Item is greater than current middle
  else {
      return binarySearch(data, item, middle + 1, high);
  }
}

Recursion and Linked Lists

• Many operations for linked lists can be completed using recursion

Recursion and Other Data Structures