Trees and Recursion
> Click or hit ControlEnter to run Example.main above
Happy Halloween!
Ready for some spooky Java?
Trees
In computer science, a tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
Trees: Parent and Child
Each parent has one or more children.
Trees: Parent and Child
Each parent has one or more children. Each child has one parent.
Trees: Root and Leaves
We refer to the top of the tree as the root.
Trees: Root and Leaves
We refer to the top of the tree as the root. We refer to nodes without any children as leaves.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
The depth or height of a tree is the maximum distance from root to leaf.
What Are Trees For?
What kinds of data can we represent using trees?

The Java class hierarchy 1

Files on your computer

Domain names on the internet

Any data that has a hierarchical structure.
Java Class Hierarchy
public class Pet { }
public class Dog extends Pet { }
public class Cat extends Pet { }
public class OldDog extends Dog { }
Your Computer’s Files
$ cd / && ls l
System
Library
Users
$ cd Users && ls l
challen
Shared
$ cd challen && ls l
classes
www
Domain Name Translation
Binary Trees
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
public class Tree {
Object value;
Tree right;
Tree left;
}
We are rarely interested in trees only for their structure. Usually we use them to structure data.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Recursion
Recursion occurs when a thing is defined in terms of itself or of its type.
public class Tree {
Object value;
Tree right;
Tree left;
}
Recursion in Computer Science
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.
Recursion v. Iteration
So far we’ve pursued iterative algorithms in this course. Recursion provides us with a new way to approach problems.

Iteration: repeat the same set of steps over and over again

Recursion: break a larger problem into smaller problems until they are small enough to solve easily
Tree Node Counting
Let’s say that we wanted to count the number of nodes in the tree above.
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
> Click or hit ControlEnter to run Example.main above
Recursive Implementation
int factorial(int n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n  1); // I called myself!
}
}
We refer to a function that calls itself as a recursive function.
> Click or hit ControlEnter to run the code above
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
Announcements

I have office hours today from 10AM–12PM. Please come by!

Note that we will have class on the Friday before Thanksgiving but not on the Wednesday before Thanksgiving. As usual, the calendar is uptodate.

We’ve added an anonymous feedback form to the course website. Use it to give us feedback!