What is iteration ? Iteration is a Computer Science term that simply means repeating a set of actions. Iteration is also called repetition or looping . The statements that are used in iteration are called loops .
Iteration, however, is not the same as selection. Beginning programmers often attempt to use a selection statement where they should use a loop, and vice versa. It is important to be able to distinguish the two, and equally important to be able to select the right control structure for the job.
The selection structure works much like the illustration shown here. Driving down a divided highway, you come to a rest stop, and you pull off. When you leave the rest stop, you rejoin the highway a little further down the road.
Once you rejoin the highway, you have no opportunity to go back, and revisit the rest stop again. Those who bypass the turnoff, skip the rest stop altogether.
A loop structure looks similar, but not the same. As you can see in this illustration, there is still a boolean test, as there is with selection. But, after you've had your break, the rest stop exit road "loops back" [hence the name], and you rejoin the highway right where you initially left it.
If you like, you can choose to enter the rest stop once again, even though the highway is one-way. In this sense, a loop also works a little bit like a cloverleaf interchange.
C++ has three loop statements, the while loop, the do - while loop, and the for loop. As you might expect, each of these loops varies in the way that it is used, and the place where it is most effectively employed.
One difference between the loops is where the test takes place--that is, the relative position of the loop test, and the actions contained in the loop body.
This is called a "test at the bottom" loop. It is also sometimes called a hasty loop or an unguarded loop, because it "leaps before it looks".
// Loop body
The other two loops, the for loop and the while loop, both make their boolean test before performing the actions in the loop body.
With these loops, if the test condition is false , then the actions inside the loop body are never performed at all. Thus, they are both guarded loops.
Counted and Indefinite
Classifying loops according to where their condition is tested helps keep the C++ syntax straight in our minds, but it's not really as useful as classifying loops by the kind of bounds that they employ.
A loop's bounds are the conditions under which it will repeat its actions. In a simple, counter controlled loop, the bounds might be expressed as "the counter has a value less than ten". In other, more complex loops, the bounds may be a combination of conditions involving ANDs and ORs.
There are two major kinds of loops that can be built using the basic building blocks [ for , while , and do - while ] provided by C++. Let's look at them briefly, before we start looking at code in the next lesson.
Counting or Counted Loops
A counting , [or counted ], loop is a loop that repeats a fixed number of times--a "gimme fifty pushups" kind of loop.
With a "pure" counting loop you can look at the code and tell how many times it should execute. In real life, however, things are not so clear-cut. You often won't know what the actual number of repetitions is until your program runs. The number of repetitions may be based upon the number of characters in a String , for instance, or some other number which is not computed until your program runs.
With an indefinite loop, you can never tell how many times the loop will repeat by examining the code. An indefinite loop is a loop that tests for the occurrence of a particular event, not a count of the number of repetitions.
"Read characters until you encounter a period" is an example of an indefinite loop. The condition may occur after reading three characters, or it may occur after reading three-thousand. It's also possible that the period might be the first character read or, sometimes, that a period might not occur at all.
There are three commonly encountered types of indefinite loops that you should be aware of. Each of these indefinite loops uses a different sort of bounds:
Writing perfect code the first time is something of a "Holy Grail" among programmers. By that I mean that most programmers long to do it, but the vast majority consider its attainment to be the stuff of legend.
Writing loops is one area where programming errors often crop up. Several years ago, however, I happened upon a technique developed by Doug Cooper, the Berkeley professor of " Oh! Pascal " fame, for building loops. This technique really does increase your chances of building correct loops the first time, and it's worth your time to learn it.
The Three Faces
The first step in building a successful loop is to be able to describe [and separate] the loop's bound from the loop's goal .
Here's an example:
We can use the same bounds with a different goal: Print each character in a String until a period is encountered. Here, the bounds is the same, but the goal is different. We're not counting, we're printing.
Step 1 Determine the Bounds
That's where you should always start writing your loops; ask yourself: "What will make this loop quit?"
"How do I get out of here?" Making sure your loops can quit is the single most important thing that you can do. Let's take our first example in the previous section, and write the loop bounds in psuedocode:
WHILE C IS NOT A PERIOD
Step 1, writing the bounds, makes sure that it is possible to get out of the loop. When you write this portion you'll have to make sure your boolean condition is not unavoidable or impossible, just as you did with selection statements.
Now that you've convinced yourself that it's possible to exit the loop, you have to write the statements that make it possible to enter the loop. Step 1 asks "How do I get out?" , while Step 2 asks "How do I get in?"
Precondition statements usually involve creating variables and initializing them to some reasonable state. In our example, we have two variables C , which is a character, and S , which is a String .
Before you encounter the loop bounds, you must make sure that C holds one of the characters in S , otherwise, you have no assurance that you will ever enter the loop--the value in C will be unknown.
In pseudocode, we could write this as:
Suppose, for instance that we didn't put any statements inside the loop body used here. What would happen?
To avoid an endless or "dead" loop, you must make sure that the statements on the inside of the loop body change something that is tested in the loop bounds.
In this case, that's as simple as storing the next character in the String S in the variable C , like this:
WHILE C IS NOT A PERIOD
ASSIGN NEXT CHARACTER IN S TO C
At this point, the mechanical portion of your loop--the part that makes it "work", so to speak--is finished. You should be able to compile your code [provided you wrote it in a programming language, of course], and it should run correctly.
The whole purpose of a loop, however, is to get some real work done, to accomplish the goal. Up until now, we've ignored the goal portion entirely, because we want to make sure the loop works , before we put it to work .
When writing the code to carry out the goal of the loop, you start at the precondition, move to the loop body, and then deal with the post condition. You don't have to worry about the post condition while programming the mechanical operation of the loop, but it is often significant when it comes to the loop's goal.
Here's what to do:
Here's the finished pseudocode for our loop:
COUNTER IS AN INTEGER, INITIAL VALUE ZERO
WHILE C IS NOT A PERIOD
ADD ONE TO COUNTER
ASSIGN NEXT CHARACTER IN S TO C
COUNTER HOLDS NUMBER OF CHARACTERS IN SENTENCE
The first loop we're going to look at is the for loop. Both Pascal and Basic have for loops, as do C and C#. Like those languages, the for loop in C++ is designed for writing counted loops--loops that repeat a specified number of times.
Unlike the Pascal or Basic for loop, however, the for loop in C++ can do much more than simple counted loops. The for loop in C++ is a general purpose, "test at the top" loop, that makes writing counted loops very straightforward, but can be used for other purposes
As mentioned previously, the body of the for loop follows the loop's test condition; you test first, then, if the test evaluates to true, you enter the loop body, as you can see in the illustration. [click image to enlarge]
The for loop's condition involves more than a simple boolean test, however. In fact, it involves three different expressions:
The loop body following the loop condition is usually enclosed in braces, although, technically, braces are not required if the loop body consists of a single statement. As a practical matter, though, you'll almost always use braces, and, since they don't hurt--even when not strictly required--you should always put them in as a matter of course.
Let's return to the for loop condition, and take a closer look at each of its three expressions
When a for loop is encountered, the first part of the loop condition, the initialization expression, is executed. It is always executed, regardless of the other parts of the for statement, almost as if it occurred on the previous line.
The initialization expression is evaluated only once, and is usually used to define the counter variable that will control your loop, like this
Variables declared inside the for loop initialization section, like counter , shown here, are local to the body of the for loop. Once the loop is finished, the variable goes out of scope and can no longer be used.
The second section of the for loop is called the test condition . The test condition is a boolean expression which is evaluated immediately after the initialization expression.
If the test condition is true , [when it is evaluated], then execution begins with the first statement in the loop. If it is false , then the entire loop body is skipped, and execution continues at the first statement following the loop body.
To continue our example, we can test the value of counter , checking to make sure it is less than ten:
Using counter like this insures that the loop will execute ten times. This is a common idiom in C++ programming:
An idiom is just a common and widely accepted way of "phrasing" a particular operation. This particular idiom works well, because you can immediately tell how many times the loop will execute just by glancing at the test condition.
In Lesson A, "Introduction to Loops", you learned to make sure that every repetition of a loop moves closer to the loop bounds. But, in the for loop shown here, there are no statements that move toward the bounds; in fact, as written, this example is an endless loop ! Since counter is never updated, it always remains at zero.
Updating the counter is the responsibility of the third part of the for loop condition--the update expression . The update expression is evaluated after the body of the loop is finished, but before the test expression is evaluated for the next repetition.
For a counted loop, you'll use the test expression to update your counter like this:
You've probably noticed that this loop doesn't really do anything; the portion that we've written simply repeats ten times. However, you can use this basic skeleton for any loop that needs to repeat a fixed number of times. Simply replace 10 with the number of times you want to repeat, and you're all set.
In addition to acting as a loop control, you can also use your counter variable to process different pieces of information during each repetition of the loop. Here, for instance, is a loop that sums the ascii values for all the characters in a String :
using namespace std;
cout << "Enter a string and I will sum all of the characters " << endl;
int sum = 0;
for(int i = 0; i < str.length(); i++)
cout << "The sum of all the characters is " << sum << endl;
Not only can you count up and count down, you can also count by values other than 1, simply by changing the value in the update expression. The Basic language allows you do do this via its STEP clause, but the C++ for loop allows you to use any expression you like, not just different constant values.
Here, for instance, is how you could calculate the sum of all the even numbers less than 100:
Notice that i is set to str.length() - 1? This is because everything in computer science is 0 based and str.length() returns the number of characters. For instance the string "test" has 4 characters in it and that is what length() would return but these chracaters are indexed 0 to 3 which also gives us for characters. Also notice the test condition is i >= 0 this is becuse we want to count the 0th character. If you run the program both ways you will see that the result is the same.
The for loop makes writing counted loops very easy because it puts the pieces you need--a place to initialize your counter, a place to test your counter, and a place to update your counter--all within easy reach.
You can do exactly the same thing with C++'s simpler, but more general-purpose while loop. It's just not quite as convenient.
To use the while statement to build a counted loop, you must do three things:
// Update loop counter
For the while loop, however, you must define and initialize your counter outside the while loop. This has several implications:
A counted while loop lends itself to endless loops in a way that the others don't. Because the while loop places the counter update expression at the bottom of the loop--which may be far removed from the while loop condition by the time all of the intervening statements have been added--it is easy to forget it.
With the for loop, leaving out the update expression creates an "empty" looking loop condition, but not with the while loop.
The easiest solution to this problem is to use the loop-building strategy presented in Lesson A, "Introduction to Loops". If you start by first writing the "mechanics" of the loop--bounds, precondition, and update--you are less likely to get distracted by the "real" statements and forget to add the update expression at the end of the loop.
If you put a semicolon after the condition of a while [or for ] loop, the body of the loop becomes the null statement. Here's an example:
Because of the semicolon, you are saying "As long as cups is less than ten, do nothing". This creates two problems:
That's true for counted loops; if you are going to write loops that are controlled by a counter, you should probably use the for loop. But, not all loops, or even most loops, are counter-controlled. Event controlled loops are much more common, and there, the while loop reigns.
A number is called a perfect number if by adding all the positive divisors of the number (except itself), the result is the number itself.
Six is the first perfect number. Its divisors (other than the number itself: 6) are 1, 2, and 3 and 1 + 2 + 3 equals 6. Other perfect numbers include 28, 496 and 8128.
Using a counted loop can you check to see if a number is a perfect number? Check your solution with the video below
In this lesson, you'll learn how to write loops that monitor events, rather than loops that use a simple counter to control their execution. To accomplish this, you'll return to the while loop which you met at the end of the last lesson.
Although the for loop is the undisputed champ in the counted-loop arena, the while loop really comes into its own when the loop test condition is a little less clear-cut.
A couple of new things here. First, the rand() function returns a pseudo-random number in the range from 0 to RAND_MAX. RAND_MAX is a constant that is defined in stdlib.h. Files with the extension .h are called header files and they contain definitions. You would normally include it the same way you do iostream
You may be thinking that you don't see this file included anywhere within the code. The truth is that iostream references it so it is like you have included it yourself. The default value of RAND_MAX is dependent upon the machine it is on. We can generate a random between 0 and whatever number you choose by using the % (modulus) operator. In the code above random numbers are being generated in a range between 0 and 99. This is something you should try to remember is that you always want to add 1 to the max number you want to get. If I wanted numbers between 0 and 100 I would have to % the number with 101.
is a way to seed the random number generator. The random number generator uses a mathematical equation to calculate random numbers. If you were to print out enough random numbers using the rand() function, you would notice that at some point the numbers repeat and that there is a pattern to them. To generate more randomness into the formula, we can seed the random number generator. This is what the srand function does. You can pass almost any value to the random number generator but you can make it more random by seeding it with the tick of the time of day clock. This is where the time() function comes in.
To use the time function you must first include ctime. it is also part of the C++ standard library. So the line of code:
says seed the random number generators mathematical calculation with a number generated by the time of day clock.
Back To Loops
Can you tell how many times this loop will execute? Probably not, unless you have some kind of psychic powers. That's why this kind of loop is called an indefinite loop. You can't tell by reading the source code how many repetitions it will make.
Even though this is not a counted loop, the body of the loop must still contain code that advances the loop's bound. If it does not, then, once entered, the loop will repeat for ever. In this example, we advance toward the loop's bound by calculating a new random number .
This particular indefinite loop is an example of a sentinel loop. A sentinel loop is a loop that looks for some special value to end the loop. The special value is called the sentinel . As mentioned earlier, sentinels are commonly used in two situations:
In the above example, the sentinel is the number 50, generated by the random number generator, and it is used to mark the end of valid input.
A sentinel doesn't always have to be a single value; it may include a range of values. For instance, here is a problem statement that calls for a sentinel loop, but a simple sentinel value would be insufficient
Rather than just reading ahead, why don't you see if you can apply what you learned in Lesson A, "A Loop-building Strategy", to create a loop that meets these requirements. When you're done, come on back here and we'll tackle it together.
Here are the questions you should ask yourself:
Let's look through the answers together:
At this point, you should be able to test the mechanics of your loop, and make sure that it "works." Once the loop works, you can turn your attention to the loop's goal.
Here's a program that follows this strategy to calculate the average of a stream of numbers. This example is a little different than the first example because, instead of using a single sentinel--the number zero, for instance--it uses a range of sentinels--any number less than zero--to mark the end of valid input.
using namespace std;
int count = 0;
double sum = 0.0;
int num = 0;
cout << "Enter an integer, negative to quit" << endl;
cin >> num;
while (num >= 0)
// Loop actions
sum += num;
cout << "Enter an integer, negative to quit" << endl;
cin >> num;
if (count > 0)
cout << "Count = " << count << " Sum = " << sum << " Avg = ";
cout << sum/count << endl;
cout << "No numbers entered" << endl ;
So far, all of the indefinite sentinel loops we've looked at have been primed loops:
Because assignment is an operator in C++, and not a statement, there is a much shorter and more concise way to write the same kind of sentinel loop. A loop employing an inline test is an extremely common C++ idiom, and you should become familiar with it, even if you prefer the longer, more traditional primed loop.
Using an inline test, the loop in the first program can be rewritten like this:
Now, you only have to initialize num once--during the loop test--and not twice--before and at the end of the loop.
Note the additional set of parentheses surrounding the assignment operation:
(num = rand() % 100)
The parentheses are required because the precedence of the relational operator [ >= ] is higher than the precedence of the assignment operator. If you omit the parentheses, C++ will compare the number it returns with zero, generating a boolean value. When it comes time to assign the boolean value to the variable num , however, C++ will choke because num is an int , and you cannot assign a boolean value to an int .
Sentinel bounds are often used to search for a particular value in a set of data, such as looking for a particular word or character in a document. When used like this, however, sentinel-controlled loops have one great failing: they can't ensure that the value will actually be found.
To handle this problem, you need to add an additional item to your loop-building toolkit--you must learn to differentiate between intentional and necessary bounds. Here's the difference.
Suppose you want to search the String s , for the character c , and return the position where the value is found. Using a simple sentinel loop you could write:
while ( (ch = s[i++]) != c )
This bounds, ch != c , is your intentional bounds , it is the sentinel value that will end your loop if all goes well. You can't just assume that all will go well, however. It is possible that:
In this example, we can handle the first necessary bounds by changing the loop condition like this:
while ( (ch = s[i++]) != c && i < strlen(s)))
Adding necessary bounds to a loop condition means that the loop can end for two [or more] reasons, not just one. When you write the loop postcondition statements, you have to take this into account.
For instance, after this loop terminates, you can determine whether the character c was found by testing ch , to see if it is equal to c . If ch == c , then the character c was found in the String s .
The above example makes use of C strings and the strlen function. Don't concern yourself with it at this point. We are coming to this real soon so it doesn't hurt you any to see it.
In addition to the for and while loops, C++ also has a loop that performs it's boolean test after the loop body, instead of before. This loop, the do - while loop, illustrated here, will always execute the statements inside its body at least once.
The body of the do - while loop appears between the keywords do [which precedes the loop body] and while . Like all loops, the body of the do - while loop can be a single statement, ending with a semicolon, or it can be a compound statement enclosed in braces. As with the other loops, you'll have a more fulfilling life if you train yourself to always use a compound [brace-delimited] loop body.
The do - while loop's boolean condition follows the while keyword. As with all selection and iteration statements in C++, the boolean condition must be enclosed in parentheses, which are part of the statement syntax. In the do - while loop, the boolean condition is followed by a semicolon. [Unlike the while loop, where following the condition with a semicolon can lead to subtle, hard to find bugs.]
The do - while loop is often employed by beginning programmers, because, for some reason, it seems more natural. If you find yourself in this situation, however, you should think twice. 99% of the time, a for loop or a while loop can be employed to better effect than using a do - while. Using a do - while is like putting salt on your food before you taste it. In fact, it is difficult for me to think of a good situation where a test-at-the-bottom strategy is superior to "looking before you leap."
C++'s selection and iteration statements are called flow-of-control statements because they provide a highly structured method of conditionally and repeatedly executing a particular section of code.
In days past, however, before the control structures we use today, programmers still needed the equivalent of if statements and loops. Rather than relying on built-in language features, though, those iron-age programmers constructed their own flow of control statements, using the jump .
The jump statement often uses another name; even programmers who have never heard of the jump have heard of its nom de plum, the goto statement. The goto is one of C++'s reserved words, but it isn't actually implemented as part of the language.
If your dream is to arbitrarily jump willy-nilly hither-and-yon through your code, you'll have to find another programming language to accommodate you. When it comes to loop control, however, C++ hasn't abandoned the jump altogether. C++ has two statements-- break and continue --that let you do your jumping in a controlled fashion.
The break statement is used in two different circumstances, but both circumstances are quite similar.
The break statement allows you to jump out of :
Although it can be misused, allowing you to write code that is as convoluted as any produced by the goto statement, the break can sometimes be used to make your loops simpler and clearer.
Here's an example, that shows how the break statement can be used to simulate a sentinel loop that stops when the number 50 has been reached. Note that the loop bounds does not need to test for the sentinel value.
using namespace std;
int num = 0,i;
num = rand() % 101;
for(i = 0; i < 100; i++)
if(num == 50)
cout << "Random Number is " << num << endl;
num = rand() % 101;
if(i < 100)
cout << "The number 50 was encountered at iteration " << i << endl;
cout << "The number 50 did not come up " << endl;
The continue statement is a jump statement like break , but unlike break , the continue jumps back to the loop condition.
Exactly what that means depends upon the loop you're using:
The code below asks the user to input characters from the keyboard. If a digit is encountered, it gets converted and added to the sum. If the character entered is not a digit then the continue statement takes the flow of control back to the top of the loop.
using namespace std;
int sum = 0;
for(int i = 0; i < 10; i++)
cout << "Enter and integer to sum " << endl;
cin >> c;
sum += (int)c - '0';
cout << "The sum of the digits entered is: " << sum << endl;
The for loop in the above code will execute 10 times. Each time a character is entered at the keyboard, it is checked to see if it is a digit. The check uses the standard C++ library character function isdigit() which returns true if the character entered is between '0' and '9'. Remember that everything entered into the keyboard is a character, which is different from a number.
9 and '9' are different
The isdigit() returns a boolean true if the character is a digit, false otherwise.
If the character entered is a digit then it gets converted to a number by subtracting the character '0' from the character entered. The character '0' has an ascii value of 48. So the above code is equivalent to subtracting 48 from the character entered. In any case, subtracting 48 from the digit will give us the actual binary value of the character representation.
Once the character is converted, it gets added to the sum of the values.
Both break and continue work on the current loop. That means, when you are in an inner loop, a break statement only exits the inner loop, it doesn't get you out of the outer loop.
If you need to break out of both inner and outer loops, then you will have to write some logic to handle it.