Objects First

Looping Statements

One of the great contributions to society made by computers is their ability to reliably repeat mundane and boring operations thousands or millions of times without

making a mistake,
complaining of boredom,
demanding tea-breaks, holidays, etc

Programming languages provide looping statements to enable this repetitive behaviour. C has three variants:

while ( expression ) { ... }

do { ... } while ( expression );

for( expr₁; expr₂; expr₃ ) { ... }

`while` statements

A while statement instructs the machine to repeat the instructions in the statement while the expression is true.

while ( expression ) statement

statement may be either a single statement or a block.

Some examples are:

Print XXXXXXXXXX
on the output

#define N 10
int i;
i = 0;
while( i < N ) {
  printf("X");
  i++;
  }

Note the C pattern of starting the count at 0 and stopping when i is less than N. This is arises from C's numbering of array indices from 0: most C programmers write all loops in this way:

Sum the elements
of an array

#define N 10
int i;
double x[N], sum;
i = 0;
sum = 0.0;
while( i < N ) {
  sum = sum + x[i];
  i++;
  }

However, the following is equivalent to our first example and will also produce N X's:

Print XXXXXXXXXX
on the output

i = 1;
while( i <= N ) {
  printf("X");
  i++;
  }

Since a lot of our programming is done by using patterns that we all know and can recognise quickly, it's generally preferable to use one pattern for all loops. The last example is very clumsy when used for arrays, so the

i = 0;
while( i < N ) { ... }

style is preferred for all loops.

The expression that guards the loop is evaluated before the block of statements is entered. The loop continues while the expression evaluates to true.

The dreaded infinite loop
The expression is always true!

#define TRUE 1 ... while( TRUE ) { printf("X"); i++; }

Needless to say, this is probably going to be a nuisance - this program will never stop! Luckily most operating systems provide mechanisms for stopping programs like this: experienced programmers often write programs with infinite loops, novices do so all the time! However, it is important to check all loops carefully to make sure that there is a valid termination condition - to avoid the problem of the infinite loop.

Because the expression is evaluated before entering the loop, it is possible to produce a while loop whose body is never executed:

If the input is unsatisfactory,
try again!
double f( double x ) { /* Make sure that x is in the correct range */ while( (x < low) || (x > high) ) { x = read_input("Enter a value for x: "); } .... return ..... ; }

In this example, if the value of x passed to the function is already in the range (low, high) then the block following the while will not be executed.

Counting backwards

Loops usually have a loop index associated with them (i in the cases above). There is no need for this index to increment, it can decrement just as well:

Print N X's
on the output

i = N;
while( i > 0 ) {
  printf("X");
  i--;
  }

The following "trick" is commonly used by C programmers:

Function to sum n elements
of an array

double vector_sum( double x[], int n ) {
  double sum = 0.0;
  while( n-- ) {
    sum = sum + x[n];
    }
  return sum;
  }

Look carefully and see why this is correct. Note:

Firstly, the loop is executed n times, because when n becomes 0, the guarding expression is false and iteration stops.
Secondly, the array elements are accessed from the last one (x[n-1]) to the first one (x[0]).
Finally that when the postfix decrement, n-- is used, the expression is evaluated, the result is used and then the variable is decremented.
Exercise
If we had written
```
while ( --n ) { ... }
```
How many times would the loop execute?

`do` loops

Another variant of the while loop is the do loop:

do { ... } while ( expression );

This is essentially the same as a while loop, except that the expression is evaluated after the statements in the loop body have been executed. Thus a do loop is always executed at least once. Compare these two trivial examples:

Loop never executed
while( FALSE ) { ..... }

Loop executed once
do { ..... } while( FALSE );

This requires some care in writing programs:

How many X's will be output?
#define N 10 i = N; do { printf("X"); i--; } while ( i > 0 );

Arbitrary termination conditions

The termination expression may be as complex as we like. It does not even need to involve a loop index. Typical numerical mathematical techniques such as the solution of an equation by Newton's technique don't need a loop counter:

Solve f(x) = 0
by Newton's technique

df(x) returns f'(x)

#define EPSILON 1.0e-10
double solve( double guess ) {
  double x1, x2;
  do {
    x1 = guess;
    x2 = x1 - f(x1)/df(x1);
    guess = x2;
    }
  while ( abs(x1 - x2) > EPSILON );
  return x2;
  }

`for` loops

Our final form of loop (and one that we have seen before used to access array elements), is the for loop. It has three expressions:

for( expr₁; expr₂; expr₃ ) { ... }

Formally, a for statement is equivalent to:


expr₁;
while( expr₂ ) {
  ....
  expr₃;
  }

To make this clear, take a simple example. Again, we want to sum the n elements of an array: using a for loop, we write:

for(i=0;i < n;i++) {
  sum = sum + x[i];
  }

which is equivalent to:

i=0;
while( i < n ) {
  sum = sum + x[i];
  i++;
  }


expr₁;
while( expr₂ ) {
  ....
  expr₃;
  }

A key point to remember is that C assignment statements are expressions! So that the assignment statements:

i = 0;

and

i++;  /* Equivalent to i = i+1; */

are also assignment expressions.

Of course, since the three elements of a for are expressions, arbitrarily complex expressions are possible! For example,

Using multiple assignments and comma expressions makes it possible to cram a lot into a single for statement. Obvioiusly, there's a point at which the overall program becomes unintelligible, so use this capability with regard for readers of your programs!

Aborting loops: `break` and `continue`

`break`: exit from the middle of a loop

Sometimes you find that the condition which you want to use to terminate the loop is naturally evaluated in the middle of a block of statements. The code might look like this:

while( ?? what goes here ?? ) {
  /* Calculate some initial results */
  .....
  /* Based on these initial results, we know whether to continue the
     loop or not */
  if ( termination_condition ) {
     ?? /* exit the loop here */
     }
  /* but if we didn't terminate, continue the computation */
  ....
  }

C's break statement handles this situation:

while( TRUE ) {
  /* Calculate some initial results */
  .....
  /* Based on these initial results, we know whether to continue the
     loop or not */
  if ( termination_condition ) {
     /* Exit the loop with break */
     break; }
  /* but if we didn't terminate, continue the computation */
  ....
  }

Note that the if ( expression ) break; statement is supplying the loop termination condition, so that the while( TRUE ) part is perfectly reasonable and does not necessarily produce an infinite loop.

break may be used in any while, do or for loop to generate an exit from the loop at any point within the loop. If loops are nested, break exits only the immediately enclosing loop:

/* Doubly nested loop to process an nxm matrix */
for(i=0;i<n;i++) {
  for(j=0;j<m;j++) {
    a[i][j] = ....
    if ( a[i][j] < EPSILON ) break;
    ....
    }
  .... /* break statement resumes HERE */
  }

In this case, if you wanted to exit both loops, you would need two i break statements - one in each loop.

`continue`: skip the rest of the loop

A continue statement causes the rest of the loop to be skipped, but loop execution continues. Thus, whereas break can be used to supply a termination condition, continue doesn't break out of a loop and a valid termination condition must still be supplied!

while( termination_condition ) {
  s₁; s₂; ... /* Some statements */
  if ( skip_rest_of_loop ) continue;
  s₁₀; s₁₁; ... /* More statents */
  /* continue resumes here */
  }

continue is exactly equivalent to:

while( termination_condition ) {
  s₁; s₂; ... /* Some statements */
  if ( ! skip_rest_of_loop ) {
    s₁₀; s₁₁; ... /* More statents */
    }
  }

thus it is relatively rarely used. All it does is avoid a block of statements nested inside a loop - a minor simplification of the program! The break statement, on the other hand, finds many applications and will be found in most C programs somewhere or other. In fact it is necessary in switch statements, where its omission will cause unexpected results to be generated!

Key terms

iteration: A single "trip" through the statements in the body of a loop: all the statements in one iteration are executed before the loop starts a second iteration of the same statements.
infinite loop: a loop in a computer program which never terminates

Loop never* executed*	while( FALSE ) { ..... }
Loop executed once	do { ..... } while( FALSE );

Objects First

Looping Statements

while statements

Counting backwards

do loops

Arbitrary termination conditions

for loops

Aborting loops: break and continue

break: exit from the middle of a loop