Practice with Recursion
> Click or hit ControlEnter to run Example.main above
Good News, Good News
I have good news and good news…

Good news: you did well on Midterm 1!

Good news: we have a fantastic new MP for you to enjoy…

Good news: …and it’s up now.

Good news: we still have over a month left together.
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.
Review: Trees: Parent and Child
Each parent has one or more children.
Review: Trees: Parent and Child
Each parent has one or more children. Each child has one parent.
Review: Trees: Root and Leaves
We refer to the top of the tree as the root.
Review: Trees: Root and Leaves
We refer to the top of the tree as the root. We refer to nodes without any children as leaves.
Review: Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Review: Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Review: Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Review: 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.
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 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 Right Greater Than Left
Let’s find the number of nodes in our tree where the value of the right child is greater than or equal to value of the left child.
What’s Our (Recursive) Algorithm?
Recursive Tree Right Greater Than Left

Base case: We’ve reached a tree with one node. It does not have a right child or left child, so we can return 0.

Recursive step: Consider our right tree and left tree separately.

Combine results: Determine whether our right child is greater than our left child. If so, add 1 to the sum of results from our left and right child.
> Click or hit ControlEnter to run Example.main above