Practice with Recursion
> Click or hit ControlEnter to run Example.main above
Terminology Clarification
I may have inadvertently used the term O(n) analysis. A better term is big O analysis, since that doesn’t confuse it with O(n) or linear algorithm runtime.
I’ll try to be as clear as possible about this going forward.
Q7 Review: Runtime
int b(int[] array, int m) {
if (m > array.length) {
m = array.length;
}
int c = 0;
for (int i = 0; i < m; i++) {
boolean g = true;
for (int j = 0; j < m; j++) {
if (array[j] > array[i]) {
g = false;
}
}
if (g) {
return c;
}
}
return c;
}
What is the best case runtime of the algorithm implemented above?
Q7 Review: List Runtime
MysteryList list = new MysteryList();
for (int i = 0; i < 1024; i++) {
list.addToFront(i);
}
After you put timing measurements into the loop show above, you notice that each
call to addToFront
takes around the same amount of time.
This leads you to believe that this MysteryList
is probably implemented
using…
Q7 Review: List Runtime
MysteryList list = new MysteryList();
for (int i = 0; i < 1024; i++) {
list.add(i);
}
// Insert 0 at position 32
list.insert(0, 32); // Takes 1.2 microseconds
list.insert(1, 128); // Takes 4.2 microseconds
list.insert(4, 1024); // Takes 37.4 microseconds
Given the timings shown in the comments above, this MysteryList
is probably
implemented using…
Q7 Review: List Runtime
MysteryList list = new MysteryList();
for (int i = 0; i < 1024; i++) {
list.addToEnd(i);
}
After you put timing measurements into the loop show above, you notice that each
call to addToEnd
takes more and more time as i
increases.
This leads you to believe that this MysteryList
is probably implemented
using…
Q7 Review: Objects
public class Counter {
public int count = 2;
public Counter() {
count++;
}
}
public class Example {
public static void main(String[] unused) {
Counter counter = null;
for (int i = 0; i < 10; i++) {
counter = new Counter();
counter.count++;
}
System.out.println(counter.count);
}
}
When the main
method runs, what will be printed?
> Click or hit ControlEnter to run Example.main above
Recursive Add Review
Recursive Add Review

5 doesn’t have a left child
Recursive Add Review

5 doesn’t have a left child

Add 3 as 5’s left child
Recursive Add Review

5 doesn’t have a right child
Recursive Add Review

5 doesn’t have a right child

Add 10 as 5’s right child
Recursive Add Review

5 has both a right and left child
Recursive Add Review

5 has both a right and left child

Randomly choose a subtree
Recursive Add Review

5 has both a right and left child

Randomly choose a subtree

And call
add
on that subtree
Recursive Add Review

10 doesn’t have a left child
Recursive Add Review

10 doesn’t have a left child

Add 9 as its left child
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 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
Announcements

No class Friday. Enjoy Spring Break! 1

MP5 is due after break.

The early deadline is right after Spring Break.

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.