More Practice with Recursion
> Click or hit ControlEnter to run Example.main above
Welcome Back!
I hope you all had a restful weekend.
Recursive Strategies
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.
Recursive Factorial
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
Reaching Base Camp
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 ControlEnter to run the code above
Recursion v. Iteration
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 ControlEnter to run the code above
Recursive Tree Print Leaves
Let’s print only leaf nodes: those that have neither a left nor a right child.
What’s Our (Recursive) Algorithm?
Recursive Tree Print Leaves

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.
> Click or hit ControlEnter to run Example.main above
Writing Perfect Code
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.
Dead Code
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!
High Complexity
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.
Questions About Perfection?
Recursive Tree Search
Let’s determine whether a tree contains a certain value.
What’s Our (Recursive) Algorithm?
Recursive Tree Search

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.
> Click or hit ControlEnter to run Example.main above
How Could We Make This Search More Efficient?
> Click or hit ControlEnter to run Example.main above
Announcements

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.