CS115 lecture notes, Spring 1999
Week 6, Monday

The Stack
---------

What's an instance?

What's an instance of a method?

What's the stack?

In addition to keeping track of the arguments and local
variables of methods, the stack also keeps track of where
we are in the program.

When a run-time error occurs, one of the things that gets
printed is a summary of the stack.


Recursion with return values
----------------------------

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


Two ways to read this program:

1) follow the stack (draw the stack)

2) leap of faith.


Follow the stack
----------------

Pretty much what we've already seen, except that this time
there is actually a local variable (and a parameter).

Return values are shown with arrows outside the boxes.
Note that return values don't really have names, although
they might get assigned to a variable.

Leap of faith
-------------

ASSUME THAT THE RECURSIVE CALL WORKS CORRECTLY.

Convince yourself that the topmost instance will always
work correctly if all the others do.

Convince yourself that the base case works correctly.

Convince yourself that you will eventually reach the base
case.


Fibonacci
---------

  public static int fibonacci (int n) {
    if (n == 0 || n == 1) {
      return 1;
    } else {
      return fibonacci (n-1) + fibonacci (n-2);
    }
  }

In this case, because there are two recursive calls,
there are two ways to follow the stack...

1) Draw the stack dynamically, adding and removing instances.
   This is the most accurate model of execution.

2) Draw a call tree that shows all the method instances.

But the best option is the Leap of Faith.

If you assume that all the recursive calls work, can
you convince yourself that the topmost instance will do
the right thing?

Can you convince yourself that we will eventually reach a
base case?


Mathematical recursion
----------------------

Many mathematical functions are defined recursively.

Translating them into Java can be an almost mechanical
process.

Ackerman...


Example:

  public static int sum (int m, int n) {
    if (m == n) {
      return n;
    } else {
      return m + sum (m+1, n);
    }
  }

Apply the follow the stack and leap of faith techniques
to this code.