Practice with Recursion

Practice with Recursion
> Click or hit Control-Enter to run Example.main above

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.

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?

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…

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…

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…

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 Control-Enter to run Example.main above

5 doesn’t have a left child

5 doesn’t have a left child
Add 3 as 5’s left child

5 doesn’t have a right child

5 doesn’t have a right child
Add 10 as 5’s right child

5 has both a right and left child

5 has both a right and left child
Randomly choose a subtree

5 has both a right and left child
Randomly choose a subtree
And call add on that subtree

10 doesn’t have a left child

10 doesn’t have a left child
Add 9 as its left child

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 Control-Enter to run the code above

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.

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.

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 Control-Enter to run Example.main above

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.

Terminology Clarification

Q7 Review: Runtime

Q7 Review: List Runtime

Q7 Review: List Runtime

Q7 Review: List Runtime

Q7 Review: Objects

Recursive Add Review

Recursive Add Review

Recursive Add Review

Recursive Add Review

Recursive Add Review

Recursive Add Review

Recursive Add Review

Recursive Add Review

Recursive Add Review

Recursive Add Review

Recursive Implementation

Recursive Strategies

Recursive Tree Right Greater Than Left

What’s Our (Recursive) Algorithm?

Recursive Tree Right Greater Than Left

Announcements