Introduction to Recursion
> Click or hit ControlEnter to run Example.main above
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.
Not Every Binary Tree Is A Search Tree
You’ll be working with binary search trees in MP5. They have rules about where elements get added.
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

MP4 is due today at 5PM.

MP5 will be released today at 5PM.

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

My office hours continue today at 11AM in the lounge outside of Siebel 0226. I’ll need to leave at 11:30AM.