3.4 Designing Loops

Round and round she goes, and where she stops nobody knows.

TRADITIONAL CARNIVAL BARKER’S CALL

When designing a loop, you need to design three things:

  1. The body of the loop

  2. The initializing statements

  3. The conditions for ending the loop

We begin with a section on two common loop tasks and show how to design these three elements for each of the two tasks.

Loops for Sums and Products

Many common tasks involve reading in a list of numbers and computing their sum. If you know how many numbers there will be, such a task can easily be accomplished by the following pseudocode. The value of the variable this_many is the number of numbers to be added. The sum is accumulated in the variable sum.

sum = 0;
repeat the following this_many times:
	cin >> next;
	sum = sum + next;
end of loop.

This pseudocode is easily implemented as the following for loop:

int sum = 0;
 	   for (int count = 1; count <= this_many; count++)
{
	cin >> next;
	sum = sum + next;
}

Notice that the variable sum is expected to have a value when the following loop body statement is executed:

sum = sum + next;

Since sum must have a value the very first time this statement is executed, sum must be initialized to some value before the loop is executed. In order to determine the correct initializing value for sum, think about what you want to happen after one loop iteration. After adding in the first number, the value of sum should be that number. That is, the first time through the loop the value of sum + next should equal next. To make this true, the value of sum must be initialized to 0.

You can form the product of a list of numbers in a way that is similar to how we formed the sum of a list of numbers. The technique is illustrated by the following code:

int product = 1;
 for (int count = 1; count <= thisMany; count++)
{
	cin >> next;
	product = product * next;
}

The variable product must be given an initial value. Do not assume that all variables should be initialized to zero. If product were initialized to 0, then it would still be zero after the loop above has finished. As indicated in the C++ code shown earlier, the correct initializing value for product is 1. To see that 1 is the correct initial value, notice that the first time through the loop this will leave product equal to the first number read in, which is what you want.

Ending a Loop

There are four commonly used methods for terminating an input loop. We will discuss them in order.

  1. List headed by size

  2. Ask before iterating

  3. List ended with a sentinel value

  4. Running out of input

If your program can determine the size of an input list beforehand, either by asking the user or by some other method, you can use a “repeat n times” loop to read input exactly n times, where n is the size of the list. This method is called list headed by size.

The second method for ending an input loop is simply to ask the user, after each loop iteration, whether or not the loop should be iterated again. For example:

sum = 0;
cout << "Are there any numbers in the list? (Type\n"
	 << "Y and Return for Yes, N and Return for No): ";
 char ans;
cin >> ans;
 while ((ans == 'Y') || (ans == 'y'))
{
	cout << "Enter number: ";
	cin >> number;
	sum = sum + number;
	cout << "Are there any more numbers? (Type\n"
		 << "Y for Yes, N for No. End with Return.): ";
	cin >> ans;
}

However, for reading in a long list, this is very tiresome to the user. Imagine typing in a list of 100 numbers this way. The user is likely to progress from happy to sarcastic and then to angry and frustrated. When reading in a long list, it is preferable to include only one stopping signal, which is the method we discuss next.

Perhaps the nicest way to terminate a loop that reads a list of values from the keyboard is with a sentinel value. A sentinel value is one that is somehow distinct from all the possible values on the list being read in and so can be used to signal the end of the list. For example, if the loop reads in a list of positive numbers, then a negative number can be used as a sentinel value to indicate the end of the list. A loop such as the following can be used to add a list of nonnegative numbers:

cout << "Enter a list of nonnegative integers.\n"
	 << "Place a negative integer after the list.\n";
sum = 0;
cin >> number;
 while (number >= 0)
{
	sum = sum + number;
	cin >> number;
}

Notice that the last number in the list is read but is not added into sum. To add the numbers 1, 2, and 3, the user appends a negative number to the end of the list like so:

1 2 3 −1

The final −1 is read in but not added into the sum.

To use a sentinel value this way, you must be certain there is at least one value of the data type in question that definitely will not appear on the list of input values and thus can be used as the sentinel value. If the list consists of integers that might be any value whatsoever, then there is no value left to serve as the sentinel value. In this situation, you must use some other method to terminate the loop.

When reading input from a file, you can use a sentinel value, but a more common method is to simply check to see if all the input in the file has been read and to end the loop when there is no more input left to be read. This method of ending an input loop is discussed in Chapter 6 in the Programming Tip section entitled “Checking for the End of a File” and in the section entitled “The eof Member Function.”

The techniques we gave for ending an input loop are all special cases of more general techniques that can be used to end loops of any kind. The more general techniques are as follows:

A count-controlled loop is any loop that determines the number of iterations before the loop begins and then iterates the loop body that many times. The list-headed-by-size technique that we discussed for input loops is an example of a count-controlled loop. All of our “repeat this many times” loops are count-controlled loops.

We already discussed the ask-before-iterating technique. You can use it for loops other than input loops, but the most common use for this technique is for processing input.

Earlier in this section we discussed input loops that end when a sentinel value is read. In our example, the program read nonnegative integers into a variable called number. When number received a negative value, that indicated the end of the input; the negative value was the sentinel value. This is an example of a more general technique known as exit on a flag condition. A variable that changes value to indicate that some event has taken place is often called a flag. In our example input loop, the flag was the variable number; when it becomes negative, that indicates that the input list has ended.

Ending a file input loop by running out of input is another example of the exit-on-a-flag technique. In this case the flag condition is determined by the system. The system keeps track of whether or not input reading has reached the end of a file.

A flag can also be used to terminate loops other than input loops. For example, the following sample loop can be used to find a tutor for a student. Students in the class are numbered starting with 1. The loop checks each student number to see if that student received a high grade and stops the loop as soon as a student with a high grade is found. For this example, a grade of 90 or more is considered high. The code computeGrade(n) is a call to a user-defined function. In this case, the function will execute some code that will compute a numeric value from 0 to 100 that corresponds to student n’s grade. The numeric value then is copied into the variable grade. Chapter 4 discusses functions in more detail.

int n = 1;
grade = computeGrade(n);
 while (grade < 90)
{
	n++;
	grade = computeGrade(n);
}
cout << "Student number " << n << " may be a tutor.\n"
	 << "This student has a score of " << grade << endl;

In this example, the variable grade serves as the flag.

The previous loop indicates a problem that can arise when designing loops. What happens if no student has a score of 90 or better? The answer depends on the definition for the function computeGrade. If grade is defined for all positive integers, it could be an infinite loop. Even worse, if grade is defined to be, say, 100 for all arguments n that are not students, then it may try to make a tutor out of a nonexistent student. In any event, something will go wrong. If there is a danger of a loop turning into an infinite loop or even a danger of it iterating more times than is sensible, then you should include a check to see that the loop is not iterated too many times. For example, a better condition for our example loop is the following, where the variable numberOfStudents has been set equal to the number of students in the class:

int n = 1;
grade = computeGrade(n);
 while ((grade < 90) && (n < numberOfStudents))
{
	n++;
	grade = computeGrade(n);
}
 if (grade >= 90)
	cout << "Student number " << n << " may be a tutor.\n"
		 << "This student has a score of " << grade << endl;
 else
	 cout << "No student has a high score.";

Nested Loops

The program in Display 3.15 was designed to help track the reproduction rate of the green-necked vulture, an endangered species. In the district where this vulture survives, conservationists annually perform a count of the number of eggs in green-necked vulture nests. The program in Display 3.15 takes the reports of each of the conservationists in the district and calculates the total number of eggs contained in all the nests they observed.

Display 3.15 Explicitly Nested Loops

An illustration shows a code segment for “Explicitly Nested Loops.”

Each conservationist’s report consists of a list of numbers. Each number is the count of the number of eggs observed in one green-necked vulture nest. The program reads in the report of one conservationist and calculates the total number of eggs found by this conservationist. The list of numbers for each conservationist has a negative number added to the end of the list. This serves as a sentinel value. The program loops through the number of reports and calculates the total number of eggs found for each report.

The body of a loop may contain any kind of statement, so it is possible to have loops nested within loops (as well as eggs nested within nests). The program in Display 3.15 contains a loop within a loop. The nested loop in Display 3.15 is executed once for each value of count from 1 to numberOf Reports. For each such iteration of the outer for loop there is one complete execution of the inner while loop. In Chapter 4 we’ll use subroutines to make the program in Display 3.15 more readable.

Self-Test Exercises

  1. Write a loop that will write the word Hello to the screen ten times (when embedded in a complete program).

  2. Write a loop that will read in a list of even numbers (such as 2, 24, 8, 6) and compute the total of the numbers on the list. The list is ended with a sentinel value. Among other things, you must decide what would be a good sentinel value to use.

  3. Predict the output of the following nested loops:

    int n, m;
 for (n = 1; n <= 10; n++)
 	   for (m = 10; m >= 1; m −−)
		cout << n << " times " << m
			 << " = " << n * m << endl;

Debugging Loops

No matter how carefully a program is designed, mistakes will still sometimes occur. In the case of loops, there is a pattern to the kinds of mistakes programmers most often make. Most loop errors involve the first or last iteration of the loop. If you find that your loop does not perform as expected, check to see if the loop is iterated one too many or one too few times. Loops that iterate one too many or one too few times are said to have an off-by-one error; these errors are among the most common loop bugs. Be sure you are not confusing less-than with less-than-or-equal-to. Be sure you have initialized the loop correctly. Remember that a loop may sometimes need to be iterated zero times and check that your loop handles that possibility correctly.

Infinite loops usually result from a mistake in the Boolean expression that controls the stopping of the loop. Check to see that you have not reversed an inequality, confusing less-than with greater-than. Another common source of infinite loops is terminating a loop with a test for equality, rather than something involving greater-than or less-than. With values of type double, testing for equality does not give meaningful answers, since the quantities being compared are only approximate values. Even for values of type int, equality can be a dangerous test to use for ending a loop, since there is only one way that it can be satisfied.

If you check and recheck your loop and can find no error, but your program still misbehaves, then you will need to do some more sophisticated testing. First, make sure that the mistake is indeed in the loop. Just because the program is performing incorrectly does not mean the bug is where you think it is. If your program is divided into functions, it should be easy to determine the approximate location of the bug or bugs.

Once you have decided that the bug is in a particular loop, you should watch the loop change the value of variables while the program is running. This way you can see what the loop is doing and thus see what it is doing wrong. Watching the value of a variable change while the program is running is called tracing the variable. Many systems have debugging utilities that allow you to easily trace variables without making any changes to your program. If your system has such a debugging utility, it would be well worth your effort to learn how to use it. If your system does not have a debugging utility, you can trace a variable by placing a temporary cout statement in the loop body; that way the value of the variable will be written to the screen on each loop iteration.

For example, consider the following piece of program code, which needs to be debugged:

int next = 2, product = 1;
 while (next < 5)
{
	next++;
	product = product * next;
}
 //The variable product contains
 //the product of the numbers 2 through 5.

The comment at the end of the loop tells what the loop is supposed to do, but we have tested it and know that it gives the variable product an incorrect value. We need to find out what is wrong. To help us debug this loop, we trace the variables next and product. If you have a debugging utility, you could use it. If you do not have a debugging facility, you can trace the variables by inserting a cout statement as follows:

int next = 2, product = 1;
 while (next < 5)
{
	next++;
	product = product * next;
	cout << "next = " << next
		 << " product = " << product << endl;
}

When we trace the variables product and next, we find that after the first loop iteration, the values of product and next are both 3. It is then clear to us that we have multiplied only the numbers 3 through 5 and have missed multiplying by 2.

There are at least two good ways to fix this bug. The easiest fix is to initialize the variable next to 1, rather than 2. That way, when next is incremented the first time through the loop, it will receive the value 2 rather than 3. Another way to fix the loop is to place the increment after the multiplication, as follows:

int next = 2, product = 1;
 while (next < 5)
{
	product = product * next;
	next++;
}

Let’s assume we fix the bug by moving the statement next++ as indicated above. After we add this fix, we are not yet done. We must test this revised code. When we test it, we will see that it still gives an incorrect result. If we again trace variables, we will discover that the loop stops after multiplying by 4, and never multiplies by 5. This tells us that the Boolean expression should now use a less-than-or-equal sign, rather than a less-than sign. Thus, the correct code is

int next = 2, product = 1;
 while (next <= 5)
{
	product = product * next;
	next++;
}

Every time you change a program, you should retest the program. Never assume that your change will make the program correct. Just because you found one thing to correct does not mean you have found all the things that need to be corrected. Also, as illustrated by this example, when you change one part of your program to make it correct, that change may require you to change some other part of the program as well.

The techniques we have developed will help you find the few bugs that may find their way into a well-designed program. However, no amount of debugging can convert a poorly designed program into a reliable and readable one. If a program or algorithm is very difficult to understand or performs very poorly, do not try to fix it. Instead, throw it away and start over. This will result in a program that is easier to read and that is less likely to contain hidden errors. What may not be so obvious is that by throwing out the poorly designed code and starting over, you will produce a working program faster than if you try to repair the old code. It may seem like wasted effort to throw out all the code that you worked so hard on, but that is the most efficient way to proceed. The work that went into the discarded code is not wasted. The lessons you learned by writing it will help you to design a better program faster than if you started with no experience. The bad code itself is unlikely to help at all.

Self-Test Exercises

  1. What does it mean to trace a variable? How do you trace a variable?

  2. What is an off-by-one loop error?

  3. You have a fence that is to be 100 meters long. Your fence posts are to be placed every 10 feet. How many fence posts do you need? Why is the presence of this problem in a programming book not as silly as it might seem? What problem that programmers have does this question address?