More Practice with Recursion

More Practice with Recursion
> Click or hit Control-Enter to run Example.main above

I hope you all had a restful weekend.

Recursion can be hard to wrap your mind around at first. But these three strategies will help.

Know when to stop. When you identify the smallest subproblem, you must return. Otherwise your program will not terminate. This is also called the base case.
Make the problem smaller in each step. If the problem doesn’t get smaller, you will never reach the base case. This is also called the recursive step.
Combine results from your recursive calls properly.

int factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1); // I called myself!
  }
}

Base case: n == 1
Recursive step: decrement n towards 1
Combine results: multiply current n with the result of the next subproblem

int factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1); // I called myself!
  }
}

You must reach the base case. Otherwise your problem will never stop, run out of memory, and crash.

How can the code above fail to reach the base case?

> Click or hit Control-Enter to run the code above

Recursive solutions can be difficult to understand.

The goal is to write clear code, not use a particular solution technique.
If an iterative solution is more clear, use that.
Sometimes a recursive solution is much more clear.
Don’t use recursion just to be cool.
Don’t use recursion because it is fewer lines of code. Who cares? Clarity is the goal, not brevity.

> Click or hit Control-Enter to run the code above

Let’s print only leaf nodes: those that have neither a left nor a right child.

Base case: We’ve reached a tree with no left or right node. It’s also a a leaf node, so print our value.
Recursive step: Consider our right tree and left tree separately.
Combine results: Nothing to do here, just continue down the tree.

import java.util.Random;

public class BinaryTree {
  private static Random random = new Random();
  private class Node {
    private Object value;
    private Node right;
    private Node left;
    Node(Object setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinaryTree(Object[] values) {
    for (Object value : values) {
      add(root, value);
    }
  }
  public void add(Object value) {
    add(root, value);
  }
  private void add(Node current, Object value) {
    if (current == null) {
      root = new Node(value);
      return;
    }
    if (random.nextBoolean()) {
      if (current.right == null) {
        current.right = new Node(value);
      } else {
        add(current.right, value);
      }
    } else {
      if (current.left == null) {
        current.left = new Node(value);
      } else {
        add(current.left, value);
      }
    }
  }
  public String toString() {
    return toString(root);
  }
  private String toString(Node current) {
    if (current == null) {
      return "";
    }
    return "[" + current.value.toString() + "]"
      + toString(current.right) + toString(current.left);
  }
  public void printLeaves() {
  }
}
public class Example {
  public static void main(String[] unused) {
    BinaryTree binaryTree = new BinaryTree(new Integer[] {1, 2, 3, 4});
    binaryTree.printLeaves();
  }
}

> Click or hit Control-Enter to run Example.main above

Starting today we’ll be assigning a small amount of credit on each homework problem for writing "perfect" code.

Obviously we can’t tell whether your code is really perfect 1—meaning correct, beautiful, minimal, concise, readable. But for the purposes of automated checking we will consider your code not to be perfect if:

It contains dead or unreachable code.
It is overly complex compared to our solution.

public class YourBinaryTree extends BinaryTree {
  public int size() {
    return size(root);
  }
  private int size(Node current) {
    if (current == null) {
      return 0;
    }
    if (current != null) {
      return 1 + size(current.left) + size(current.right);
    } else {
      return 0;
    }
  }
}

The last return 0 will never be reached!

public class YourBinaryTree extends BinaryTree {
  public int size() {
    return size(root);
  }
  private int size(Node current) {
    if (current == null) {
      return 0;
    }
    if (current.left == null) {
      return 1 + size(current.right);
    } else if (current.right == null) {
      return 1 + size(current.left);
    } else {
      return 1 + size(current.right) + size(current.left);
    }
  }
}

There are 4 paths through size(Node current)
For the solution there are only 2.

Let’s determine whether a tree contains a certain value.

Base case: We’ve reached a node with no descendants. Return true if its value matches, zero otherwise.
Recursive step: Consider our right tree and left tree separately.
Combine results: Return true if either we or our right or left subtree contain the search value.

import java.util.Random;

public class BinaryTree {
  private static Random random = new Random();
  private class Node {
    private Object value;
    private Node right;
    private Node left;
    Node(Object setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinaryTree(Object[] values) {
    for (Object value : values) {
      add(root, value);
    }
  }
  public void add(Object value) {
    add(root, value);
  }
  private void add(Node current, Object value) {
    if (current == null) {
      root = new Node(value);
      return;
    }
    if (random.nextBoolean()) {
      if (current.right == null) {
        current.right = new Node(value);
      } else {
        add(current.right, value);
      }
    } else {
      if (current.left == null) {
        current.left = new Node(value);
      } else {
        add(current.left, value);
      }
    }
  }
  public String toString() {
    return toString(root);
  }
  private String toString(Node current) {
    if (current == null) {
      return "";
    }
    return "[" + current.value.toString() + "]"
      + toString(current.right) + toString(current.left);
  }
  public boolean search(Object value) {
    return false;
  }
}
public class Example {
  public static void main(String[] unused) {
    BinaryTree binaryTree = new BinaryTree(new Integer[] {1, 2, 3, 4});
		System.out.println(binaryTree.search(4));
  }
}

> Click or hit Control-Enter to run Example.main above

public class BinarySearchTree {
  private class Node {
    private Comparable value;
    private Node right;
    private Node left;
    Node(Comparable setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinarySearchTree(Comparable[] values) {
    for (Comparable value : values) {
      add(root, value);
    }
  }
  public void add(Comparable value) {
    add(root, value);
  }
  private void add(Node current, Comparable value) {
    if (current == null) {
      root = new Node(value);
      return;
    }
    if (current.value.compareTo(value) >= 0) {
      if (current.right == null) {
        current.right = new Node(value);
      } else {
        add(current.right, value);
      }
    } else {
      if (current.left == null) {
        current.left = new Node(value);
      } else {
        add(current.left, value);
      }
    }
  }
  public String toString() {
    return toString(root);
  }
  private String toString(Node current) {
    if (current == null) {
      return "";
    }
    return "[" + current.value.toString() + "]"
      + toString(current.right) + toString(current.left);
  }
  public boolean search(Object value) {
    return false;
  }
}
public class Example {
  public static void main(String[] unused) {
    BinarySearchTree binarySearchTree = new BinarySearchTree(new Integer[] {1, 2, 3, 4});
    System.out.println(binarySearchTree.search(3));
  }
}

> Click or hit Control-Enter to run Example.main above

Coders Chapters 8 for next week’s quiz. (Chapter 7 for this week’s quiz.)
My office hours this week will be Wednesday from 1–3PM.

Welcome Back!

Recursive Strategies

Recursive Factorial

Reaching Base Camp

Recursion v. Iteration

Recursive Tree Print Leaves

What’s Our (Recursive) Algorithm?

Recursive Tree Print Leaves

Writing Perfect Code

Dead Code

High Complexity

Questions About Perfection?

Recursive Tree Search

What’s Our (Recursive) Algorithm?

Recursive Tree Search

How Could We Make This Search More Efficient?

Announcements