Which initial value of number would cause an infinite loop?

Comments and questions to John Rowe.

In the previous lecture we learnt about logical statements that determine whether or not code gets run. Here we learn about loops which allow sections of code to run zero or more times, with a controlling logical expression.

The while() loop has the form:

The contents of the loop, which as always may be a single statement or a { ... } block, are executed for as long as the controlling expression is true.

The while() loop repeats as long as the condition is true (non-zero).

If the condition is false the body of the loop never executes at all.

This may sound slightly unintuitive (if there's nothing to do, why have a loop?) but when writing a program we often don't know if there will always be something to loop over and it would be really inconvenient to have to wrap every loop inside an if() statement.

A trivial example

In this rather contrived example, x is halved every time the loop is executed until at last the test condition is false and the loop quits. If x had started with a value of less than or equal to one the loop would not have executed even once.

If the condition is false the body of the loop never executes at all.

Mini-exercise

NB: if you have problems with this see the min-exercise in the section "Debugging loops".

1. Write a simple while() loop that reads in an integer.
2. To demonstrate a while() loop.
3. Create a new on-line program in a new window, with a suitable title and opening comment.
4. Declare an int variable and initialise it to zero.
5. Write a simple while() whose test is that the variable is greater than or equal to zero and whose body:
   1. Prints a simple message asking for an integer
   2. Then has a call to scanf() that reads the value of your variable from the keyboard. (Of the form scanf("%d", &varname) )
   • Note 1: as there is more than one statement you will need to use { and }
   • Note 2: when you run a program that uses scanf() from within the on-line compiler the console window will have two sections: type your input into the lower, darker section.
6. Build & run, enter a few positive values into the lower part of the console window, pressing <return> between each one.
7. Now type a negative number and press <return>: your program should finish.
8. Now modify your program so that the initial value of your variable is -1 (minus one). Do you think your program will ask you for any input?
9. Build & run. Check the output is correct..

In one sense while() loops are a bit more complicated and subtle than they first appear. Whilst our initial pseudo-example looks simple, it's clear that the controlling expression can't go on being true forever or else the loop would never stop. To avoid accidental "infinite loops" that never stop the loop must do something to change the value of the controlling expression. We shall refer to this as the increment.

In the above example the increment is the sole statement inside the loop x = x / 2.0; which clearly affects the controlling expression.

Another example of an increment might be a function call (covered in the next lecture) that returns a value to say if the loop should continue, or a call to scanf() (for example a loop that reads in an integer and loops until it's within a certain allowed range of values).

Although it's very unusual, it's possible for the controlling expression to contain its own increment although whether this is wise is another matter altogether.

Understanding the increment is critical to understanding the loop.

Example: a power function

We can use the while loop to write a "poor man's power function" which calculates value to the power of exponent where exponent is a positive integer. We show the core loop of program first, with the complete program following below:

Here the increment is the line exponent = exponent - 1;

1. Step through the above "Key example".
2. To observe the behavious of the increment.
3. Step through the above "Key example" in a new window.
4. Step through the code observing the change in the value of exponent.
5. Before each evaluation of the test expression exponent > 0 try to predict whether the loop will continue or not.
6. If you don't get it right first time, refresh the page and try again until you do.

Although most control expressions are fairly simple we are, of course, allowed to use all the logical operators we can use with the if() expression:

The word bug means an error in the program and debugging refers to fixing problems with the code.

Loops can easily go wrong with the most common problems being:

• Loops that never start.
• Loops that never finish.
• Loops that repeat the wrong number of times.
  

Check how a loop starts

When examining any loop it's good to ask "what would happen if the condition were false the very first time it was evaluated?". In this case we are talking about exponent == 0 in which case the loop would never execute. Thus result would be 1.0, the correct answer. If exponent == 1 the loop will execute once, making result equal to value, again the correct answer.

Mentally check how a loop starts

Check how a loop increments and finishes.

As we mentioned above, if exponent == 1 the loop will execute once, making result equal to value, again the correct answer. If exponent == 2 the loop will execute twice, making result equal to value squared, etc.

Mentally check how a loop increments and finishes.

As we discussed in the previous section, the loop above contains an "increment", i.e. a statement that does something that will affect the test the next time round (in this case it's actually a decrement, "increment" is just a generic term):

If in doubt, print it out

If we get the increment wrong the loop may never end, we will have entered an "infinite loop". The program will start and just never end or get on to the next statement. For example we have have mistakenly written:

If this happens, an easy test is to put a printf() statement inside the loop, such as:

Notice how we have printed out:

• The value of the controlling variable (exponent) and the progress of the loop (result).
  
• A description of what it is: simply printing out anonymous numbers is extremely confusing.
  

If your program starts and seems to do nothing you may have entered an infinite loop. Try putting a printf() statement in the loop and see what happens.

Another extremely useful tactic is to print out the "input" values at the start of the loop and the result at the end,

1. Add some debugging output to your previous loop
2. To demonstrate some debugging.
3. After your call to scanf() in the loop add a call to printf() to print out the value you have just read in. Make sure the printf() statement also has some helpful text so it's not just an anonymous number.

A complete program

Here is a short complete program incorporating this loop where we have highlighted the test and the increment:

The result is:

The above example has the effect that the value of the original variable "exponent" is lost (and we have somewhat artificially written the code to handle this). Often however, we need to preserve the original value and so we take a temporary copy of it. This gives the following code, where we have highlighted the temporary copy and three lines that control how many times the loop is executed:

Although this works, it's rather crude and confusing. Fortunately there is a better way.

A common pattern

If we look at the parts of the above program that control the execution of the loop we see the following:

1. Initialise: ( tmpexp = exponent; )
2. Loop:
   1. Test (tmpexp > 0 ) and if false quit the loop.
   2. Execute the body of the calculation.
   3. Increment. ( tmpexp = tmpexp - 1; )

In our case the loop goes:

Initialise .. test-loop-increment .. test-loop-increment .. test-loop-increment .. test-loop-increment .. test & quit

Notice that the initialisation happens only once for the whole loop.

This Initialise, Test, Increment loop is so common that it has a loop especially for it, the for() loop:

The for() loop rolls all these three into one. It has the following format:

Note that the three expressions are separated by semicolons, not commas, and that they occur in the same order as they are used.

for (Initialise; Test; Increment ) separated by semicolons, not commas

The steps in the for() loop are done in exactly the same order as in the equivalent while() loop:

for(Initialise; Test; Increment)

1. Initialise
2. Loop:
   1. Test and if false quit the loop.
   2. Execute the body.
   3. Increment.

Just as in the while() loop, if the for() loop test is initially false the body never executes.

Using the for() loop the program now looks like this:

Here we have chosen to removes the braces { } as there is only one statement within the loop.

The for() loop could be written a little more naturally as:

In this case they both yield the same result, although in general this is not always the case of course.

1. Step through the above "Key example".
2. To observe a for() loop.
3. Step through the above "Key example" in a new window.
4. Step through the program, particularly noting:
   • The change in the value of tmpexp
   • The successive application of the test tmpexp > 0
5. Check that you can successfully predict whether the test will be true or false. If not, refresh the page and repeat until you can.

In the loops we have written so far we have often had steps which have the same variable on both sides of the equals sign such as:

In the wages calculation in the preface we had a step:

• Add that day's pay to the running-total

This sort of phrase comes naturally to us and C provides a way of doing it directly with the += operator:

which means "add the value of days_pay to running_total". Notice there is no space between the + and the =.

When we are at the supermarket the till is constantly doing calculations of the type "add the cost of this item to the current value of the bill".

Just about any operator can have "=" after it:

running_total += days_pay; means "add the value of days_pay to running_total"

The code fragments:

can be further abbreviated to:

These last two are used quite often (particularly ++j) so try to use them whenever possible.

++j; means "add 1 to j"

There are two slightly different forms of the "++" operator. Both have the same effect when in a statement on their own but are different when used in an expression, such as an assignment.

The statement

means "add one to j and then set set k to the (new) value of j".

means "set k to the (old) value of j and then add one to j".

Exactly the same principle applies to the "--" operator.

Remember the mega-principle and avoid chances to go wrong!

I suggest you don't use "++" inside expressions: it just gives us the chance to go wrong.

Notice how we have taken the opportunity to use a descriptive variable name for our array index.

The for() (and only the for()) has a further ability: the initialiser can be replaced by a variable declaration which has effect only in that loop, including the loop body. We can therefore simplify the above example slightly:

Here we had no need to use tmpexp inside the body of the for() loop, but we could have if we had wanted to.

See the extended prime number test example.

1. Step through the above "Key example".
2. To see the two new features in action and to cement our understanding of the for() loop.
3. Step through the above "Key example" in a new window.
4. Start the above code.
5. Note how a new variable tmpexp springs into existence (with the value 4) when the loop starts.
6. Step through the code noting how both the control variable tmpexp and result change in value.
7. Note how tmpexp disappears when the loop finishes.
8. Make sure you understand the test-loop-increment sequence and that you can correctly predict what the loop will do next.
9. As always, Refresh the page and go through it again until you can confidently get it right.

The Initialiser of a for() loop can declare a temporary variable which exists only as long as the loop runs.

1. Write a simple for() loop.
2. To practice writing a for() loop.
3. Create a new on-line program in a new window, with a suitable title and opening comment.
4. Write a simple for() loop to print out the squares of the numbers zero to ten inclusive.
   • Your code should have an increment that increases the value of your control variable by one each time.
5. Build & run. Check the output is correct..
   • If your code doesn't work use the etchniques in the "Debugging loops" section.
6. Now convert your code so that it prints out the values in reverse order (from ten squared down to zero squared) using a negative increment that decreases the value of your control variable by one each time.

The final, and least used, of C's loops, the do { ... } while();, behaves in exactly the same way as the more widely used while() { ... } loop except that the body of the loop is executed before the logical test, meaning that the loop always executes at least once. The basic format is:

Notice the semi-colon after the while().

Example: successive halving.

The chances are you will never have to use this loop in this module so don't worry too much about it.

In the last lecture we met the break statement which breaks out of a switch() statement. The break statement can also break out of a loop (but not an if()).

The break statement breaks out of the innermost switch() statement or loop (but not an if()).

The continue statement

The continue statement goes to the next iteration of the innermost loop (but not an if()).

That is to say, for the while() and do { ... } while(); loops the continue statement goes straight to the next evaluation of the control statement and quits the loop if it evaluates to zero. For a for() it evaluates the increment and then the control statement and quits the loop if that evaluates to zero.

The break statement gives us another way to quit a loop and in some circumstances it may be most convenient to deliberately create a loop whose control expression will never be zero and to have a break statement inside it. The following example continues until the user enters a negative number.

Other popular ways to create an infinite loop include:

and

Note we have still got the two semi-colons inside the for(;;).

This works because in a for() loop if the test is absent it is assumed to be true. The apparent weakness of this construction (it looks strange!) is also its strength: it look so strange it's hard to mistake it for anything else.

Summary

The text of each key point is a link to the place in the web page.

1. Initialise
2. Loop:
   1. Test and if false quit the loop.
   2. Execute the body.
   3. Increment.