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 .
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.
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.
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++)
The initial
expression
is
executed once,
before anything else in the 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. |
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
.
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 int
s 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.
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.
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.
The boolean expression If the condition is 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.
There are a number of well-recognized loop categories, a couple of which we outline here
When you know how many times to iterate. All the loops we have shown so far are count-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).
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
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).
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. isPrime
function using (a) a while loop and (b) a do-while loop.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
.