CS 4:  Lecture 18
                           Wednesday, March 22, 2006

Binary search
-------------
Recall that when a method calls itself recursively, Java's internal stack holds
two or more stack frames connected with that method.  Only the top one can be
accessed.

Here's a recursive method that searches a sorted array of ints for a particular
int.  Assume i is an array of ints sorted from least to greatest--for instance,
{-3, -2, 0, 0, 1, 5, 5}.  We want to search the array for the value "findMe".
If we find "findMe", we return its array index; otherwise, we return FAILURE.

We could simply check every element of the array, but that would be slow.
A better strategy is to check the middle array element first.  If findMe is
lesser, we know it can only be in the left half of the array; if findMe is
greater, we know it can only be in the right half.  Hence, we've eliminated
half the possibilities with one comparison.  We still have half the array to
check, so we check the middle element of that half, and so on, cutting the
possibilites in half each time.  Suppose we search for 1.

  -------------------
  | -3 -2 0 0 1 5 5 |
  ----------^--------
   compare with 0 |  
                  |  
                  v  
            ---------
            | 1 5 5 |
            ----^----
              | compare with 5
              |      
              V      
            -----
            | 1 |    
            -----    

The recursion has two base cases.
(1)  If findMe equals the middle element, return its index; in the example
     above, we return 4.
(2)  If we try to search a subarray of length zero, the array does not contain
     "findMe", and we return FAILURE.

  public static final int FAILURE = -1;

  private static int bsearch(int[] i, int left, int right, int findMe) {
    if (left > right) {
      return FAILURE;                   // Base case 2:  subarray of size zero.
    }
    int mid = (left + right) / 2;            // Halfway between left and right.
    if (findMe == i[mid]) {
      return mid;                                     // Base case 1:  success!
    } else if (findMe < i[mid]) {
      return bsearch(i, left, mid - 1, findMe);            // Search left half.
    } else {
      return bsearch(i, mid + 1, right, findMe);          // Search right half.
    }
  }

  public static int bsearch(int[] i, int findMe) {
    bsearch(i, 0, i.length - 1, findMe);
  }

STACK    bsearch    left [4]             |
                   right [4]  findMe [1] |
                     mid [4]       i [.]-+---------\
         --------------------------------|         |
         bsearch    left [4]             |         |
                   right [6]  findMe [1] |         |
                     mid [5]       i [.]-+---------|
         --------------------------------|         |
         bsearch    left [0]             |         |
                   right [6]  findMe [1] |         |
                     mid [3]       i [.]-+---------|
         --------------------------------|         |
         bsearch  findMe [1]       i [.]-+---------|   -------------------
         --------------------------------|         \-->| -3 -2 0 0 1 5 5 |
         main                   args [.]-+->["in"]     ------------------- HEAP


How long does binary search take?  Suppose the array has n elements.  In one
call to bsearch, we can eliminate half the elements from consideration.  Hence,
it takes log_2 n (the base 2 logarithm of n) bsearch calls to pare down the
possibilities to one.  Binary search takes time proportional to log_2 n.

Stack Size
----------
Most operating systems give a program enough stack space for a few thousand
stack frames.  If you use a recursive procedure to perform a million-iteration
loop, Java will try to create a million stack frames, and the stack will
run out of space.  The result is a run-time error.  You should use iteration
instead of recursion when the recursion would be very deep.

However, our recursive binary search method does not have this problem.  Most
modern microprocessors cannot access more than 2^64 bytes of memory.  Even if
an array of bytes takes this much space, we will only have to cut the array in
half 64 times to run a binary search.  There's room on the stack for 64 stack
frames, with plenty to spare.  In general, recursion to a depth of roughly log
n (where n is the size of a problem) is safe, whereas recursion to a depth of
roughly n is not.

Mutual Recursion
----------------
Mutual recursion occurs when two or more methods create a cycle by calling each
other.

  static long gcd(long a, long b) {
    if (b == 0) {
      return a;
    } else {
      return gcdHelper(a, b);
    }
  }

  static long gcdHelper(long a, long b) {
    return gcd(b, a % b);
  }

The gcd method can call the gcdHelper method, which calls gcd again.  There's
no reason to write a GCD algorithm this way.  But mutual recursion is useful
for some tasks, like parsing English sentences.  In English, a sentence can
have an object, which can be modified by a subordinate clause, which can have
an object of its own, and so on.

  Dorothy killed the wicked witch, who flew on a broomstick, which I used to
  sweep my house, which is painted green.

For this reason, computer programs for parsing often use mutual recursion.

  void parseClause(String[] clause) {  |  void parseObject(String[] object) {
    ...                                |    ...                              
    if (clauseHasObject) {             |    if (objectHasClause) {           
      parseObject(object);             |      parseClause(clause);           
    }                                  |    }                                
    ...                                |    ...                              
  }                                    |  }                                  

You can also have a method w that calls x, which calls y, which calls z, which
calls x.  The bottom line is that recursion is happening if one method has two
or more stack frames on the stack at the same time.

The Hardest Midterm Question
----------------------------
What is the output of this program?

public class What {
  public long n;

  public void increment() {
    n++;
  }

  public static void reset(What w) {
    w.increment();
    w = new What();
    w.n = 0;
  }

  public static void main(String[] args) {
    What w = new What();
    w.n = 7;
    reset(w);
    System.out.println("The number is " + w.n);
  }
}

Just after the line "n++;" executes, memory looks like this.

STACK                                         |                            HEAP
                                              |
method call      parameters & local variables |
----------------------------------------------|
                                     ---      |
What.increment                  this |.+---------------------\
                                     ---      |              |
----------------------------------------------|              |
                                     ---      |              |
What.reset                         w |.+---------------\     |
                                     ---      |        |     |
----------------------------------------------|        v     v
                            ---      ---      |       ----------
What.main              args |?|    w |.+------------->|  n | 8 | What object
                            ---      ---      |       ----------
----------------------------------------------|

Then, reset() creates a new object and sets its "n" field to zero.

----------------------------------------------|
                                     ---      |       ----------
What.reset                         w |.+------------->|  n | 0 |
                                     ---      |       ----------
----------------------------------------------|
                            ---      ---      |       ----------
What.main              args |?|    w |.+------------->|  n | 8 |
                            ---      ---      |       ----------
----------------------------------------------|

However, this has no effect on the first "What" object.  So the output is 8.