CS115 lecture notes, Fall 1999
Week 6, Wednesday

READING: Chapter 6

Recursion
---------

What does the following program do?

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

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


Multiple assignment
-------------------

int fred = 5;
fred = 7;

1) Old value replaces new.

2) You can assign a value as many times as you want,
   but you can only declare once.

int fred = 5;
int fred = 7;    // ERROR

3) You can change the value of parameters by assigning
   values to them, but it is almost never a good idea.

   Of course, changing the value of a parameter has no
   effect on the caller (who provided the original values,
   but has no interest in the final values).


Iteration
---------

Doing things repeatedly in programs is so common that there
is a program construct for it.

It is not necessary, since we already know how to iterate using
recursion, but it is sometimes easier to write iterative programs.

WARNING: we are going to look at many algorithms that can be
implemented using recursion OR iteration, but we are not going
to look at any that do BOTH (although there are lots).  Therefore,
if you find yourself iterating AND recursing, something is
very wrong!


The while statement
-------------------

1) the syntax is identical to a simple if statement

   while (condition) {
     body
   }

2) The condition has to be a boolean expression

3) The body can contain any kind of statement, including
   declarations, assignments, method invocations, if statements,
   and even while statements

4) The semantics are almost like the English:

   While the condition is true, keep repeating the body
   over and over until the condition becomes false.

5) Iterative structures are called loops.  Each time the
   loop is executed is called an iteration.


Example
-------

  public static void countup (int n) {
    int i = 0;
    while (i <= n) {
      System.out.println (i);
      i = i+1;
    }
    System.out.println ("Blastoff!");
  }

In this case i is called a loop variable, because it is the
variable that keeps track of the iterations and determines
when the loop terminates.


Infinite loops
--------------

Somehow or other, the body of the loop should do something
that eventually makes the condition false.

If the condition is always true, the loop will run forever,
which is usually not what you want.

This requirement is similar to what I said about recursive
methods, which is that you have to make sure you reach the
base case eventually.

In some cases, we can't tell whether the method will terminate.

  public static void sequence (int n) {
    while (n != 1) {
      System.out.println (n);
      if (n%2 == 0) {           // n is even
        n = n / 2;
      } else {                  // n is odd
        n = n*3 + 1;
      }
    }
  }

But most of the time you can.