Copyright © 1997 Kenneth J. Goldman

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.


while ( boolean expression ) {

   loop body


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.


int fact(int n) {

   if (n == 0)

      return 1;


      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).

nk product

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.


Recall the recursive solution:

int expt(int n, int k) {

   if (k == 0)

      return 1;


      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 = ni

   int i = 0;

   int n_to_the_i = 1;

   while (i < k) {


      n_to_the_i *= n;


   // on termination, i=k, so by the

   // loop invariant, n_to_the_i = nk

   return n_to_the_i;


Of course, we need to check that:
  1. The loop invariant is true initially, and after each iteration of the loop (safety).
  2. The loop will eventually terminate (liveness).
We won't actually do these proofs in CS101, but you'll learn how in CS201.



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) {


      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;



Iteration in Graphics

Let's do some examples of loops in graphics programs:
  1. 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));
          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;
  2. 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 =;   // get the first position
    while (room.inside(p)) {
       p =;   // (What would happen if we omitted this line?)
  3. 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 sequence
    squares(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