CS151 lecture notes, Fall 1999
Week 5, Friday

Quiz 7.


Booleans
--------

Named after Boole, who invented an algebra (Boolean algebra)
that is based entirely on two values, sometimes called 0 and 1,
true and false, or high and low.

Since computers are based on a binary number system, there is
a natural connection between computing and Boolean algebra.

In Java:

1) the result of a comparison is a boolean value.

2) you can assign the result of a comparison to a boolean variable.

  public static boolean isFrabjuous (int x) {
    boolean frabjuousFlag = (x > 0);
    return frabjuousFlag;
  }

3) a boolean method can return the result of a comparison directly!

  public static boolean isFrabjuous (int x) {
    return (x > 0);
  }

  This makes it really obvious that isFrabjuous is just testing
  for positive numbers.

4) You can use any boolean expression as a condition inside an
   if statement, and that includes invoking methods that return
   boolean.

   if (isFrabjuous (x) && isHoopy (x)) {
     println ("x is hoopy and frabjuous");
   }

5) The logical AND operator (denoted &&) in Java, is true
   only if both operands are true.

   The logical OR operator (||) is true if either operand
   is true, and also true if both are.

   The logical NOT operator (!) operates on a single operand.
   The result is the opposite of the operand.

   ! is pronounced BANG.

6) WARNING:  there are also operators denoted & and | that
   operate on both booleans and integers.  On booleans, they
   do the same thing as && and ||.

   What they do to integers is too horrible to speak.


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.