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

Good news: you did well on Midterm 1!

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

Bad news: it won’t be ready until Monday, but that means…

Good news: you have a weekend off! Enjoy it.

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 Add
Recursive Add

5 doesn’t have a left child
Recursive Add

5 doesn’t have a left child

Add 3 as 5’s left child
Recursive Add

5 doesn’t have a right child
Recursive Add

5 doesn’t have a right child

Add 10 as 5’s right child
Recursive Add

5 has both a right and left child
Recursive Add

5 has both a right and left child

Randomly choose a subtree
Recursive Add

5 has both a right and left child

Randomly choose a subtree

And call
add
on that subtree
Recursive Add

10 doesn’t have a left child
Recursive Add

10 doesn’t have a left child

Add 9 as its left child
> Click or hit ControlEnter to run Example.main 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
Questions About Recursion?
CS 125 Project Fair
Fair Overview
This will be our second CS 125 Final Project Fair: bigger and better than ever.

Date: Thursday 12/13/2018, Reading Day

Participation: Optional but worth 1% extra credit

Location: TBD, but probably in the Illinois Union with awards following in Foellinger.
How to Not Get a Great CS Job
All of you will get a job. Not all of you will get a great 1 job.
Here’s a good strategy for not getting a good job:

Take CS classes.

Do the projects.

Get good grades.

Don’t do any side projects: focus on grades instead.
How to Get a Great CS Job
Show your passion for technology.

The CS 125 Project Fair is intended to get you started doing that.
Example Spring 2018 Fair Projects
Announcements

MP5 will be out Monday morning.

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!