Nearly all algorithms involve repetition of some sort. Often, the number of repetitions is not known at the time of writing the program, but depends instead on the input values or the size of the input.

So far, we've handled repetition through recursion. We've
directly handled part of the work and made a recursive call to
handle the rest. Examples include not only numerical
algorithms, like `factorial`

, but also algorithms for
traversing data structures. We would, for example, do something
with the first item of the list and then combine it with the
result of a recursive call on the rest of the list.

Although recursion is often the most natural way to think about
algorithms that involve repetition, there is another approach,
known as **iteration** (or, more commonly,
loops).

To support iteration, Java provides a construct called the
`while`

loop.

**Syntax:**while ( boolean expression ) { loop body }

**Semantics:**- If the boolean expression, known as the
**test**, evaluates to`true`

, the loop body is executed, and execution continues at the top of the loop, where the test is evaluated again. The loop terminates when the test fails (evaluates to`false`

).

Usually, some initialization takes place before entering the loop. Let's go back to some algorithms we implemented using recursion and see how they could be implemented using loops.

Recall:

int fact(int n) { if (n == 0) return 1; else return (n * fact(n - 1)); }Using a loop, we can write:

int fact(int n) { int k = 0; int product = 1; // initialization while (k < n) { // test k = k + 1; product = product * k; // loop body } return product; }

Although people don't use flowcharts much in CS anymore, let's think about the execution of this example using one.

The loop terminates when the test fails, and execution proceeds
immediately to the statement following the loop. So, in this
case, when *k*=*n*, the loop terminates, and
execution continues at the `return`

statement.

Let's consider the variable values at each step of the
iteration, finding `fact(4)`

.

`n` | `k` |
`product` |
---|---|---|

4 | 0 | 1 |

4 | 1 | 1 |

4 | 2 | 2 |

4 | 3 | 6 |

4 | 4 | 24 |

Notice that when we start the loop, and at each iteration,
*product*=*k*! . This kind of expression, that is
always true of the loop variables, is known as a **loop
invariant**.

Using the loop invariant together with the termination
condition, we can determine if the return value is correct. In
this example, the loop terminates when *k*=*n*.
So, if *k*=*n* on termination, and
*product*=*k*! is the loop invariant, then
substituting, we know that *product*=*n*! on
termination.

Let's do another example, but this time we'll write the loop
invariant **before** writing the loop, so we can
use it to **guide** us in writing a correct
program.

int expt(int n, int k) { if (k == 0) return 1; else return (n * expt(n, k-1)); }Now let's write an iterative solution:

int expt(int n, int k) { // loop invariant: n_to_the_i = nOf course, we need to check that:^{i}int i = 0; int n_to_the_i = 1; while (i < k) { i++; n_to_the_i *= n; } // on termination, i=k, so by the // loop invariant, n_to_the_i = n^{k}return n_to_the_i; }

- The loop invariant is true initially, and after each
iteration of the loop (
**safety**). - The loop will eventually terminate
(
**liveness**).

Recall:

int fib(int n) { // assume n > 0 int k = 1; int fibk = 1; int fibk_1 = 0; // loop invariants: fibk = fibonacci(k) // fibk_1 = fibonacci(k-1) while (k < n) { k++; int fibk_2 = fibk_1; fibk_1 = fibk; fibk = fibk_1 + fibk_2; } // on termination, k=n, so by the // loop invariant, fibk = fibonacci(n) return fibk; }

- Drawing a rectangle and subdividing the rectangle into
*n*pieces (needs*n*-1 lines):void dividedRectangle(int x, int y, int width, int height, int n, CS101Canvas screen) { screen.add(new Rect(x, y, width, height)); int i = 1; double sizeOfSlice = ((double) width) / n; double iPosition = x + sizeOfSlice; // position of line 1 while (i < n) { screen.add(new Line(iPosition, y, iPosition, y + height)); i++; iPosition += sizeOfSlice; } }

Another way to accomplish this, without the counter`i`

:void dividedRectangle(int x, int y, int width, int height, int n, CS101Canvas screen) { screen.add(new Rect(x, y, width, height)); double position = x; double sizeOfSlice = ((double) width) / n; while (position < x + width) { screen.add(new Line(position, y, position, y + height)); position += sizeOfSlice; } }

- Suppose you want to add a loop to your
`designRoom`

procedure in Lab 3, so the couch potato can rearrange the room by clicking on new positions for the TV. Now we have to decide When the loop should terminate. Let's say when the user clicks outside the room. (Assume that`screen`

,`room`

, and`myTV`

are already initialized and that we have a`moveTo`

method on the`TV`

class that repositions it at the given center position.)Position p = screen.click(); // get the first position while (room.inside(p)) { myTV.moveTo(p); p = screen.click(); // (What would happen if we omitted this line?) }

- Consider a procedure to draw concentric squares:
void squares(int x, int y, int size, CS101Canvas screen) { if (size > 0) { screen.add(new Rect(x, y, size, size)); squares(x + 5, y + 5, size - 10); } }

So, for example,`squares(0, 0, 35)`

would produce the call sequencesquares(0, 0, 35) squares(5, 5, 25) squares(10, 10, 15) squares(15, 15, 5) squares(20, 20, -5)

and draw: Now, using iteration:void squares(int x, int y, int size, CS101Canvas screen) { while (size > 0) { screen.add(new Rect(x, y, size, size)); x += 5; y += 5; size -= 10; } }

Kenneth J. Goldman Last modified: Sun Mar 30 20:11:11 CST 1997