CS231 lecture notes, Fall 1998
Week 3, Monday

Reading: Standish Chapter 4 (skim 4.4)

Primitives and protected access
--------- ---- ----------------

Look at call graph for List class

Only primitives access the instance variables; higher-level
methods do not.

Methods in other class definitions should not.

Java provides language features to enforce restrictons.

Making instance variables private is a common solution, although
it might not provide exactly what you want.

Providing accessor methods lets you select read only, write only
and read/write instance variables.

There's also "protected," whatever that is.


Quiz!
-----

Solution:

  public boolean inList (ListNode goal)
  {
    for (ListNode node = head; node != null; node = node.next) {
      // in this case, shallow equality is the right test
      if (node == goal) return true;
    }
    return false;
  }


Recursion
---------

One of the reasons people find recursion difficult is that there are
many different ways to look at it.  The book shows several of them.

Last semester, I suggested two ways to read recursive programs:

1) follow the stack: each time a method invokes itself, create
   a new frame for the new method invocation, including fresh
   versions of the arguments and local variables

2) leap of faith: when you get to the recursive call, assume that
   the invocation works correctly 


Example:

public int factorial (int n)
{
	if (n==0) return 1;
	return n * factorial (n-1);
}

a) draw the stack for n=2
b) make the leap of faith argument

public int product (int m, int n)
{
	if (m == n) return m;
	int middle = (m+n) / 2;
	return product (m, middle) * product (middle+1, n);
}

a) preconditions
b) is (m+n)/2 always in (m,n)
c) call graph looks like a tree


Next time: list reversal!