Recursion Part 2

More Recursion Examples

GCD - Euclidean Algorithm

• The greatest common divisor (GCD) is the largest value that evenly divides into two numbers
• Explanation of Euclidean Algorithm

Iterative Solutions to GCD

# Division based
def gcd(a, b):
  while b != 0:
    tmp = b
    b = a % b
    a = tmp
  return a

or

# Subtraction based
def gcd(a, b):
  while a != b:
    if a > b:
      a = a - b
    else:
      b = b - a
  return a

Recursive Solution to GCD

def gcd(a, b):
  if b == 0:
    return a
  else
    return gcd(b, a % b)

Sierpinski Triangle

• http://lodev.org/cgtutor/sierpinski.html
• Draw a triangle
• For each upward facing triangle, recursively connect the midpoints of each triangle to create a new triangle
• Also see: http://www.mi.sanu.ac.rs/vismath/bridges2005/burns/index.html

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) {
  return sequentialSearch(data, item, 0);
}

private 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
• Bases cases generally involve determining if we've found a specific node, or if we're reached the end of the list

Recursive get(int index)

public E get(int index) {
  // Empty list or invalid index
  if(this.size == 0 || index < 0 || index >= this.size) {
    return new NoSuchElementException();
  }

  return get(index, 0, this.head);
}

private E get(int index, int currIndex, LinkedNode<E> node) {
  // At the given index
  if(index == currIndex) {
    return node.getData();
  }
  
  // Keep advancing
  return get(index, currIndex + 1, node.getNext());
}

Recursive indexOf(E item)

public void indexOf(E item) {
  if(this.size == 0) {
    return -1;
  }
  return indexOf(E item, this.head, 0);
}

private void indexOf(E item, LinkedNode<E> node, index) {
  // Item not in list
  if(node == null) {
    return -1;
  }

  // Found item
  if(node.getData().equals(item)) {
    return index;
  }

  // Try the next item
  return indexOf(item, node.getNext(), index + 1);
}

Recursive toString()

@Override
public String toString() {
  if(this.size == 0) {
    return "[]";
  }
  return "[" + toString(this.head);
}

private String toString(LinkedNode<E> node) {
  // Found last node in list
  if(node.getNext() == null) {
    return node.getData() + "]";
  }

  // Store this nodes data, and recursively concatenate next node
  return node.getData() + "," + toString(node.getNext());
}

Recurive add(E item) (adds to end of singly linked list)

public void add(E item) {
  if(this.size == 0) {
    this.head = new LinkedNode<E>(item);
  }
  else {
    add(item, this.head);
  }
  this.size++;
}

private void add(E item, LinkedNode<E> node) {
  // Have we reached the end of the list?
  if(node.getNext() == null) {
    node.setNext(new LinkedNode<E>(item));
  }
  else {
    add(item, node.getNext());
  }
}

In-Class Work

• Implement the following methods for both a singly linked list and a doubly linked list
• public void add(E item, int index)
• public E remove(E item)