A loop is the only control-flow construct that lets you go back to an earlier point in the code. Loops are designed to allow us to iterate—to repeat executing the same piece of code over and over again.

We'll consider three different kinds of loops, but first, we have to consider a couple of new operators .

Increment and Decrement

Incrementing (adding 1 to) a number and decrementing (subtracting 1 from) are so common that they have their own special operators, ++ and --. Thus

i++

means add 1 to i and

i--

means subtract 1 from i.

We'll have more to say about these operators later.

For Loops

Here is a simple for loop

    for (int i = 0; i < 5; i++)
        cout << i << '\t' << i*i << endl;

which produces the following output

0    0
1    1
2    4
3    9
4    16

In essence, a variable i is created and set to 0, then, as long as it is less than 5 the statement following is executed, printing out a line with the value of i, a tab and then i2. After that, i is incremented and then tested. The process is repeated so long as it is less than 5.

The single statement after the parentheses is called the body of the loop. Just as with if and else clauses a loop body can either be a single statement or a statement block. Inside the parentheses after the keyword for are three expressions separated by semi-colons.

  1. The initialization expression (int i = 0) is executed once, before any other part of the loop. The scope of any variable declared in it (i in this case) extends just to the end of the loop.
  2. The loop continuation condition (i < 5) is an expression that is evaluated before the body of the loop is entered. It must evaluate to a bool. If it is true, the body of the loop is executed. If it is false the loop is exited and execution proceeds to the next instruction after the for loop.
  3. Despite the fact that the update expression (i++) appears in the code before the loop body, it is not executed until after the loop body.

Here's an example of a function that uses the for loop to compute the factorial of a number.

One of the things that gives students trouble when they start out is that computer code is written on a page (effectively in space), but when it runs it does so in time.

The following table shows a diagram on the left tracing the code flow—how the code evolves in time. In the commentary to the right, we show the line of as it appears on the page, except the various parts have been colour coded to try to help you see what code parts correspond to what time sequences.

 

for (i = 2; i <= num; i++)
     fact *= i;

The initial expression is executed once, before anything else in the for loop.

The loop continuation condition is executed before the body of the loop.

After the body of the loop the update expression is executed

After the update expression is executed, we go back and test the loop continuation condition again

As soon as the condition is false, the flow of control moves to the statement immediately after the loop.

Example: Prime Number Check

A prime number is a number that is only divisible by 1 and itself. How can we test whether a number is prime?

A simple approach is to try dividing the number by all other numbers starting from 2. How high should we go? Well, any factor greater than the square root of the number will have to be paired with a factor less than its square root. Thus, we could write an isPrime function as follows.

Note that the square root is calculated before the loop is entered. The alternative would be to write

for(int i = 2; i <= sqrt(num); i++)

The trouble with this is that the test is carried out every time i is incremented so that the square root function is called repeatedly, That is both expensive and unnecessary, so a root variable has been created instead. This is one typical use of variables, to hold values returned from function calls for later re-use.

Notice also the boolean flag variable prime. Since every number up to root is being tested, it is necessary to keep track of the fact that a factor has been found. Otherwise, you're stuck with the result of the last test. For example, if 14 were being checked it would be divided by 2 and then 3. 2 divides evenly but 3 doesn't so the fact that 2 did has to be flagged.

Of course, it would be even better to quit once we know for sure that a number is not prime. Here's a version that does just that.

This version takes advantage of the fact that the moment a return statement is executed it forces an exit from the function even if there is code after it. Thus the only way the final return can be reached is if no value from 2 to root divides evenly into num. If even one did it would force the early return.

Example: Poker Hand Combinations

Here's a nice little example that exposes the dangers of blindly applying formulae. Suppose we would like to know how many different five card poker hands can be dealt from a deck of 52? The standard mathematical formula is known as 52C5 , the number of combinations of 52 things taken 5 at a time. The standard formula is

nCr = n! / ( (n-r)!r! )

Applying the formula is straightforward. We simply adapt our previous example.

When we run it, however, we get a nonsensical answer. If you step through the example in the Teaching Machine carefully, recording its answer and comparing it to a calculator, we can generate the following table:

num num! TM
1
1
1
2
2
2
3
6
6
4
24
24
5
120
120
6
720
720
7
5,040
5,040
8
40,320
40,320
9
362,880
362,880
10
3,628,800
3,628,800
11
39,916,800
39,916,800
12
476,001,600
476,001,600
13
6,227,020,800
1,932,053,504

The TM tracks up to 12! then goes awry. A problem in its code? Not at all. 13! gives us a number that's too big for our int type to hold. Remember, we said ints had a limited range. The Teaching Machine uses 32 bits (4 bytes) to represent integers, but half of those are for negative nos. Thus the max positive no. is 231 = 2,147,483,648

What the TM has done is to wrap around like an odometer on an old car that reads 35,000 kilometres when it has actually gone 135,000.

To solve the problem, we notice that 52!/(47! * 5!) = 52*51*50*49*...../(47*46*45*....*5!) = 52 * 51 * 50 * 49 * 48/5!. Only the first five nos. of the largest factorial need be multiplied because the rest get divided out by 47!

So can we write a loop to do that? Of course, here it is.

Notice the extra test. This is because 52C5 and 52C47 are actually the same (because of symmetry). But calculating 52 * 51 * 50 * .... * 5 would still be too big.

Notice also that we are counting down instead of up. The for loop lets us go whichever way is most convenient for our problem

Finally, there are extra big integers called long integers which might be big enough to handle 52! Still, our second algorithm takes fewer calculations to make and so uses less resource to get the same answer. The most reliable approach would be to use our new algorithm and long integers as well.

A Design Problem: Fibonacci Numbers

Create a function to deliver the nth Fibonacci number. The Fibonacci series is created by starting with 0 and 1 and then creating each new number by adding the previous two in the sequence together. The n'th Fibonacci number is the n'th one in the sequence.

if n is 0 F0 is 0

if n is 1 F1 is 1

let Flast be F1 that is 1

let F2ndlast be F0 that is 0

for i = 2 to n

Fi = Flast + F2ndlast

F2ndlast = Flast

Flast = Fi

The key to this algorithm is that Flast and F2ndLast are constantly changing

Here is the code.

While Loops

A while loop is created by a while statement. For example the factorial loop could also be written

long fact = 1;
while (num > 1){
    fact *= num;
    num--;
}

which computes the factorial by working downwards from num to 2. The while loop has a loop continuation condition and a body. As long as the condition is true the body keeps executing. Note that since there is no update expression, programmers must take care to include their own in the body of the loop. The condition is always looked at before the body is executed so it is possible to have a case where the body is never executed (because the codition is false from the get-go).

The control flow for the example in the syntax definition looks like this. Once again we colour code it to allow you to correlate the time sequence on the left with the code itself.

fact = 1;
while (num > 1){
     fact *= num;
     num--;

}

The boolean expression num > 1 represents a loop continuation condition

If the condition is true the body of the loop is executed.

After the body is executed, we go back and (test the loop continuation condition again

As soon as the condition is false, the flow of control moves to the statement immediately after the loop.

Let's run the full code in the Teaching Machine.

Loop Categories

There are a number of well-recognized loop categories, a couple of which we outline here

Count-Controlled Loops

When you know how many times to iterate. All the loops we have shown so far are count-controlled loops.

Event-Controlled Loops

Iteration continues until some event occurs in the body of the loop. Consider the problem of evaluating the well known p series:

åk=1k=¥ 1/kp = 1 + 1/2p + 1/3p + 1/4p + ...

This series is known to converge for p > 1.

In this case, the event is that the new term falls below a predefined threshold. The prime2 program had a loop that was both count controlled and event controlled (because it returned the moment a divisor is found).

Loop Design

  1. The general case:
  2. The special cases:

Notice we have put the general case first. Although it may seem counter-intuitive (because when you read the code the while or the for precedes the body of the loop)

Design loops from the inside out (from the general to the specific).

Note the implication here is that

  1. first design the loop, then
  2. code the loop

Do While Loops

Our final kind of loop.

A do-while loop is created by a do-while statement . It is really just a variant of the while statement. The difference is that the test condition comes after the body of the loop which means that the body of the loop will always be executed at least one time. This is often used to test inputs. Consider the main function from the prime number examples.

We asked the user to enter a positive number but there is no way to enforce that. do-while loops are perfect for that.

In the new version the input and prompt are put inside a do-while loop, forcing them to be executed at least once. If the number is entered correctly the loop exits. On the other hand, if is less than 2, it cycles back and tries again (and keeps doing so until the number meets the criterion).

Exercises

  1. In the first example, for_loop.cpp, there was a factorial funtion which computed factorial(num) using a for loop. However the main function also used a loop to produce a table to test the function. The double looping is redundant. Create a single function to print out a table of factorials from 1 to n, where n is an argument. It should only have a single for loop in it and should not call any other functions.
  2. Rewrite the original isPrime function using (a) a while loop and (b) a do-while loop.
  3. The prime3.cpp program will loop on the input value until the user puts in a correct value. However, the prompt gives the user no hint what the error is. Can you fix up that piece of code to do a better job prompting?
  4. The integral of f(x) from x = a to x = b can be approximated by n trapezoids, each of width deltaX = (b-a)/2. The i'th trapezoid has a left edge height f(xi) and a right edge height of f(xi+1). Write a function for computing the integral with arguments a, b and n, assuming the function f(x) has been declared and written (you don't need to know what f(x) is). You may assume b > a.

Note the following relationships: there are n trapezoids but n+1 endpoints. Number the trapezoids from 0 to n-1 and the end points from 0 to n. Then x0 = a and xn = b and xi+1 = xi + deltaX. We don't actually have to have all n endpoints at once. Instead we'll calculate the area of each trapezoid starting with the leftmost, then moving right, calculating and adding each new area as we go. Thus, there are really only two x values to worry about, the left and right values for the trapezoid being worked on.

So we only need two x variables—call them xLeft and xRight. For trapezoid 0 xLeft = a and xRight = xLeft + deltaX.

Examples Shown in Full