CSC152 2004F, Class 13: Loops

Admin
* Happy new year!
* Danger: It's Friday and it's the 13th
* Note about difficulty of 152.
* Homework 13 due: Modify various vector classes.
* Homework 14 assigned: More testing of vectors.
  * Why -4pi to 4pi?  Because some things work wrong outside of the normal range of values.

Overview:
* Discussion of homework
* An alternative conditional
* Loops, in general
* while loops
* for loops

/Random Question/

* With what you know now, can you do repetition (e.g., for HW14)?
  * Use recursion!
  public void checkAngleLessThan4Pi(double angle)
  {
    if (angle < Math.PI*4) {
      // Check!
      dafasdfasdasdf();
      // Go on to the next value
      this.checkAngleLessThan4Pi(angle + Math.PI/16);
    }
Hidden moral of 151: Recursion is the most natural way to repeat actions.
Response of most programmers: Hah!

/Part of homework: Reduce the angle of a Polar thingy to 0 <= angle < 2Pi./

	public void fixAngle()
	{
		// NO!  Infinite recursion.  1: fixAngle();  
		if (this.angle < 0) {
			// NO!  Infinite recursion for neg angle.  2: fixAngle();
			this.angle += 2*Math.PI;
			3: fixAngle();
		}
		else if (this.angle >= 2*Math.PI) {
			// NO!  4: fixAngle();
			this.angle -= 2*Math.PI;
			5: fixAngle();
		}
		// NO!  Any angle that doesn't satisfy those two conditions is already okay, so why recurse?  6: fixAngle();
	}

	public void fixAngle()
	{
		if (this.angle < 0) {
			this.angle += 2*Math.PI;
			this.fixAngle();
		}
		else if (this.angle >= 2*Math.PI) {
			this.angle -= 2*Math.PI;
			this.fixAngle();
		}
	}

	public void fixAngle()
	{
		if (this.angle < 0) {
			this.fixNegativeAngle();
		}
		else if (this.angle >= 2*Math.PI) {
			this.fixPositiveAngle();
		}
	}

Problem: What if the angle is bigger than 4PI or smaller than -2Pi?
The program does not magically decide to call fixAngle() again.
See repair above.

Problem with recursive call: If we already know that it's too small, why bother checking if it's big?  (Ignore that problem ... check again just to be safe.)
* See second repair above.

Note:
	x += y is shorthand for "x = x+y"
	x -= y is shorthand for "x = x-y"

/An alternative to if/

	switch (integer-valued-expression) {
		case value1:
		  BODY;
		  break;
		case value2:
		  BODY;
		  break;
		default:
		  BODY;
		  break;
	}

	Evaluate the expression
	if it matches value1, do BODY1 and stop
	if it matches value2, do BODY2 and stop
	if it matches value3, do BODY3 and stop

Using switch in GraduateAssistant

	public void printQuadrant(Vec2D vec)
	{
		int quad = vec.getQuadrant();
		// quad is now 0, 1, 2, 3, or 4.
		// meaning of 0: on an axis
		// meaning of another number: in that quadrant
		if (quad == 0) 
			pen.println("on an axis");
		else if (quad == 1)
			pen.println("first quadrant");
		...
	} // printQuadrant(Vec2D)
	public void printQuadrant(Vec2D vec)
	{
		int quad = vec.getQuadrant();
		// quad is now 0, 1, 2, 3, or 4.
		// meaning of 0: on an axis
		// meaning of another number: in that quadrant
		switch (quad) {
			case 0:
			  	pen.println("on an axis");
				break;
			case 1:
				pen.println("first quadrant");
				break;
			case 2:
				pen.println("second quadrant");
				break;
			case 3:
				pen.println("third quadrant");
				break;
			case 4:
				pen.println("fourth quadrant");
				break;
			default:
				pen.println("lost in space (r)");
				break;
		} // switch
	} // printQuadrant(Vec2D)

The gain is not in what you can express ... the gain is how
nicely you can express it.

Variant
	case VAL1:
	case VAL2:
		BODY
		break;
	if the value is val1 or val2
		switch (quad) {
			case 0:
			  	pen.println("on an axis");
				break;
			case 1:
			case 3:
				pen.println("odd quadrant");
				break;
			case 2:
			case 4:
				pen.println("even quadrant");
				break;
			default:
				pen.println("lost in space (r)");
				break;
		}

/On to repetition/

* Reminder: Recursion suffices, but some people find it "inelegant" or "inexpressive" or "inefficient"
* Detour: Why do tail recursion?  
  * "So you don't have to run every part of a procedure every time."
  * Feels like we save some steps.
* Detour, continued: What is tail recursion?  
  * As part of tail recursion, we often accumulate some result.
  * In tail recursion, every recursive call has no additional context (you do not do anything with the result of a recursive call but return it)
* Detour, continued: Why do tail recursion?
  * A tail-recursive procedure doesn't have to remember anything about itself when doing the recursive call.
  (define sum (lambda (lst)
    (if (null? lst) 0
        (+ (car lst) (sum (cdr lst))))))
  This is not tail recursive.  Each procedure needs to remember to add the car of the list after the recursive call is done.
* Why not do recursion?
  * Too much recursion can result in loss of memory.  "stack overflow"
  * In some langauges, there is a lot of overhead every time you do a function call: Recurision involves function calls and therefore slows down the program.
* Note:
  * Tail recursion does not result in loss of memory, since you don't need to save what to do next.
  * When implemented correctly, tail recursion does not involve the same overhead as a regular function call.
* The alternative?  Loops.
* Three kinds of loops:
  * Indefinite number of repetitions, possibly 0: while
  * Indefinite number of repetitions, but at least 1: do/while
  * Fixed number of repetitions: for

  Syntax of while loop

  	while (TEST) {
	  BODY
	}
	NEXT_STATEMENT

  Meaning of while loop
	1. Evaluate the TEST.
	2. If the TEST is true
	   a. Execute the BODY
	   b. Go back to step 1.
	3. If the TEST is false
	   a. Go on to NEXT_STATEMENT

	   while (this.angle < 0) {
	   	this.angle = this.angle + 2*Math.PI;
	   }
* Important issues:
  * Body may never be executes
  * The test gets reexecuted at every step.
  * If there is no next statement, it's "done" with the current task after the loop.

Alternative, for one or more repetitions
	do {
		BODY
	} while (TEST);

Meaning
	1. Execute the BODY.
	2. Evaulate the TEST
	3. If the TEST is true, go back to 1.
	4. If the TEST is false, done with the loop
Important issues:
* Guarantees one repetition
* Some people don't use them much.
* Common with input.
	do {
		ch = keyboard.readChar();
		...
	} while (ch != 'q')

For loops, easy case
	for (int i = START; i < END; i += 1) {
		BODY
	}
MEANING:
	set i to START, then START + 1, then START + 2, ... up to END (non-inclusive)
	Execute BODY for each value of i.
Shorthand:
	i++ is the same as "i += 1" is the same as "i = i + 1"

For loops, general case
	for (INITIALIZE; TEST; INCREMENT) {
		BODY;
	}
meaning
	INITIALIZE;
	while (TEST) {
		BODY;
		INCREMENT;
	}
In particular
	for (int i = 0; i < 10; i++) {
		pen.println(i);
	}
is
	int i = 0;
	while (i < 10) {
		pen.println(i);
		i++;
	}
Advantage of "for" over "while" in this case?
* Somewhat easier to read.  In the second, it's hard to tell just when the body stops and the increment begins.

	for (double angle = -4*Math.PI; angle <= MATH.pi; angle += MATH.pi/16) {
	}