CS115 lecture notes, Spring 1999
Week 5, Monday

Quiz on Chapter 4.

Reading for this week:  Chapter 5

Recursion
---------

Methods can invoke themselves, and it is often useful to
do so.

Of course, if they invoke themselves EVERY time, then it
will never stop.  So eventually it has to stop.

  public static void countdown (int n) {
    if (n == 0) {
      System.out.println ("Blastoff!");
    } else {
      System.out.println (n);
      countdown (n-1);
    }
  }

Normally (if n is not zero) this method is recursive.

But if n is zero, it does NOT make the recursive call,
so eventually the process terminates.

What's an instance?
-------------------

If you have a category (like feline things), then a member
of the category (like my cat Boris) is sometimes called an
instance.

When you invoke a method, you create an instance of that
method.  The instance contains a copy of the parameters and
any local variables.

With recursive methods, there can be more than one instance
at the same time.

In the example, there are 4 instances: the one that received
3 as an argument, and the ones that received 2, 1, and 0.

Method invocations terminate (or return) in the opposite of
the order they appear.

Often we draw state diagrams of method invocations by drawing
stacks of boxes.  Each box is an instance of a method.

The boxes get added and removed from the bottom of the stack
(just a convention that people got used to).

A useful recursion
------------------

  public static void nLines (int n) {
    if (n > 0) {
      System.out.println ("");
      nLines (n-1);
    }
  }

The documentation of this method claims that it takes one
parameter, and that it prints that parameter the given number
of times.

If the values of the argument is zero, the method does nothing,
which is correct: it printed zero new lines.

What if the argument is one?  two?  three?

Can you convince yourself that this method will work in
general?

Draw a state diagram of the method invocations when n=3.


Generalization
--------------

How can we generalize nLines so that it can print any String
the given number of times?

  public static void nTimes (int n, String fred) {
    if (n > 0) {
      System.out.println (fred);
      nLines (n-1);
    }
  }

Very few changes.  Good chance of working the first time.

Starting with something specific and gradually making it more
general is a good "program development plan."

Much better than trying to write the most general version
all at once.  Very hard to debug.

How does this apply to the Snowpeople project?

Notice that fred is getting passed from one instance to
another without being modified.  This behavior is fairly
common -- often you have to use parameters just to get
information from one part of a program to another.

The Graphics object named g is like that -- it gets passed
all over the place as an argument.


Fruitful methods
----------------

Consider multadd:

  public static void multadd (double a, double b, double c) {
    System.out.println (a * b + c);
  }

Now this is useful if we happen to want to print the result,
but it is more likely that we would like to get the result
and store it in a variable, as in

    int result = multadd (1.0, Math.log (10.0), Math.log (20.0));

In order to do that, we have to transform multadd into a
FRUITFUL method...

  public static double multadd (double a, double b, double c) {
    double result = a * b + c;
    return result;
  }

Two changes:

1) return type is double (not void)

2) return statement takes an expression that specifies the
   value we want to return

   The return value can be any expression, as long as it
   has the promised type:

  public static double multadd (double a, double b, double c) {
    return a * b + c;
  }