6.1. While-Statements

We have seen that the sequential flow of a program can be altered with function calls and decisions. The last important pattern is repetition or loops. There are several varieties. The simplest place to start is with while loops.

A C# while loop behaves quite similarly to common English usage. If you hear

While your tea is too hot, add a chip of ice.

Presumably you would test your tea. If it were too hot, you would add a little ice. If you test again and it is still too hot, you would add ice again. As long as you tested and found it was true that your tea was too hot, you would go back and add more ice. C# has a similar syntax:

while ( condition )
statement

As with an if statement we will generally assume a compound statement, after the condition, so the syntax will actually be:

while ( condition ) {
statement(s)
}

Setting up the English example as pseudocode in a similar format would be:

while ( your tea is too hot ) {
add a chip of ice
}

To make things concrete and numerical, suppose the following: The tea starts at 115 degrees Fahrenheit. You want it at 112 degrees. A chip of ice turns out to lower the temperature one degree each time. You test the temperature each time, and also print out the temperature before reducing the temperature. In C# you could write and run the code below, saved in example program cool/cool.cs:

1
2
3
4
5
6
int temperature = 115;
while (temperature > 112) { // first while loop code
   Console.WriteLine(temperature);
   temperature = temperature - 1;
}
Console.WriteLine("The tea is cool enough.");

We added a final line after the while loop to remind you that execution follows sequentially after a loop completes.

It is extremely important to totally understand how the flow of execution works with loops. One way to follow it closely is to make a table with a line for each instruction executed, keeping track of all the variables, playing computer. as with if statements, the executed lines that you show in your table will not be in textual order, as in Sequential Execution. While if statements merely altered execution order by skipping some lines, loops allow the same line in the text of your program to be executed repeatedly, and show up in multiple places in your table.

If you play computer and follow the path of execution, you could generate the following table. Remember, that each time you reach the end of the block after the while heading, execution returns to the while heading for another test:

Line temperature Comment
1 115  
2   115 > 112 is true, do loop
3   prints 115
4 114 115 - 1 is 114, loop back
2   114 > 112 is true, do loop
3   prints 114
4 113 114 - 1 is 113, loop back
2   113 > 112 is true, do loop
3   prints 113
4 112 113 - 1 is 112, loop back
2   112 > 112 is false, skip loop
6   prints that the tea is cool

Each time the end of the loop body block is reached, execution goes back to the while loop heading for another test. When the test is finally false, execution jumps past the indented body of the while loop to the next sequential statement.

Note

Unless a program is purely sequential, the numbers under the Line column are not just in textual, sequential order. The order of the numbers is the order of execution. Each line number in the “playing computer” table is the line number label for the next particular line getting executed. Since in decisions, loops, and function calls, lines may be reordered or repeated, the corresponding line numbers may be skipped, repeated, or otherwise out of numerical order.

The biggest trick with a loop is to make the same code do the next thing you want each time through. That generally involves the use of variables that are modified for each successive time through the loop. Here is a general pattern:

initialization
while ( continuationCondition ) {
do main action to be repeated
prepare variables for the next time through the loop
}

The simple first example follows this pattern directly. Note that the variables needed for the test of the condition must be set up both in the initialization and inside the loop (often at the very end). Without a change inside the loop, the loop would run forever!

How to manage all of this in general is a big deal for beginning students. We will see a number of common patterns in lots of practice. We will use the term successive modification loop for loops following the pattern above.

Test yourself: Follow the code. Figure out what is printed. If it helps, get detailed and play computer:

1
2
3
4
5
int i = 4;
while (i < 9) {
   Console.WriteLine(i);
   i = i + 2;
}

Check yourself by running the example program test_while1/test_while1.cs.

Note

In C#, while is not used quite like in English. In English you could mean to stop as soon as the condition you want to test becomes false. In C# the test is only made when execution for the loop starts (or starts again), not in the middle of the loop.

Predict what will happen with this slight variation on the previous example, switching the order in the loop body. Follow it carefully, one step at a time.

1
2
3
4
5
int i = 4; //variation on TestWhile1.cs
while (i < 9) {
   i = i + 2;
   Console.WriteLine(i);
}

Check yourself by running the example program test_while2/test_while2.cs.

The line sequence is important. The variable i is increased before it is printed, so the first number printed is 6. Another common error is to assume that 10 will not be printed, since 10 is past 9, but the test that may stop the loop is not made in the middle of the loop. Once the body of the loop is started, it continues to the end, even when i becomes 10.

Line i Comment
1 4  
2   4 < 9 is true, do loop
3 6 4+2=6
4   print 6
2   6 < 9 is true, do loop
3 8 6+2= 8
4   print 8
2   8 < 9 is true, do loop
3 10 8+2=10 No test here
4   print 10
2   10 < 9 is false, skip loop

You should be able to generate a table like the one above, following the execution of one statement at a time. You are playing through the role of the computer in detail. As code gets more complicated, particularly with loops, this “playing computer” is an important skill.

Problem: Write a program with a while loop to print:

10
9
8
7
6
5
4
3
2
1
Blastoff!

Analysis: We have seen that we can produce a regular sequence of numbers in a loop. The “Blastoff!” part does not fit the pattern, so it is logically a separate part after the loop. We need a name for the number that decreases. It can be time. Remember the general rubric for a while loop:

initialization
while ( continuationCondition ) {
do main action to be repeated
prepare variables for the next time through the loop
}

You can consider each part separately. Where to start is partly a matter of taste.

The main thing to do is print the time over and over. The initial value of the time is 10. We are going to want to keep printing until the time is down to 1, so we continue while the time is at least 1, meaning the continuationCondition can be time >= 1, or we could use time > 0, since time is an integer here.

Finally we need to get ready to print a different time in the next pass through the loop. Since each successive time is one less than the previous one, the preparation for the next value of time is: time = time - 1.

Putting that all together, and remembering the one thing we noted to do after the loop, we get blastoff/blastoff.cs:

using System;

class Blastoff
{
   static void Main()
   {
      int time = 10;
      while (time > 0) {
         Console.WriteLine(time);
         time = time - 1;
      }
      Console.WriteLine("Blastoff!");
   }
}

Look back and see how we fit the general rubric. There are a bunch of things to think about with a while loop, so it helps to go one step at a time, thinking of the rubric and the specific needs of the current problem.

There are many different (and more exciting) patterns of change coming for loops, but the simple examples so far get us started.

Loop Planning Rubric

Looking ahead to more complicated and interesting problems, here is a more complete list of questions to ask yourself when designing a function with a while loop (and most will apply to later forms of loops, too):

  • What data is involved? Make sure you give good variable names.
  • What needs to be initialized and how? This certainly includes any variable tested in the condition.
  • What is the condition that will allow the loop to continue? It may be easier to think of the condition that will stop the loop. That is fine - but remember to negate it (with !) to turn it into a proper continuation condition.
  • Distinguish: What is the code that should only be executed once? What action do I want to repeat?
  • How do I write the repeating action so I can modify it for the next time through the loop to work with new data?
  • What code is needed to do modifications to make the same action code work the next time through the loop?
  • Have I thought of variables needed in the middle and declared them; do other things need initialization?
  • Will the continuation condition eventually fail? Be sure to think about this!
  • Separate the actions to be done once before the repetition (code before the loop) from repetitive actions (in the loop) from actions not repeated, but done after the loop (code after the loop). Missing this distinction is a common error!

This is quite a sequence of steps! Particularly looking forward to other forms of loops, we can note a more basic split into two parts:

  • Writing the code to make sure each desired iteration is reached (loop dynamics: initialized data for the test condition, the test condition itself, preparing for the next iteration)
  • Doing the work for a specific item/ireration (most of the body of the loop)

You generally only need to concentrate on one of those at a time. If you set up how to reach all of the repetitions, giving names for the variables to be acted on, then you can separately just concentrate on dealing with the the action/code to deal with the current situation.

6.1.1. Sum To n

Let us write a function to sum the numbers from 1 to n:

/// Return the sum of the numbers from 1 through n.
static int SumToN(int n)
{
   ...
}

For instance SumToN(5) calculates 1 + 2 + 3 + 4 + 5 and returns 15. We know how to generate a sequence of integers, but this is a place that a programmer gets tripped up by the speed of the human mind. You are likely so quick at this that you just see it all at once, with the answer.

In fact, you and the computer need to do this in steps. To help see, let us take a concrete example like the one above for SumToN(5), and write out a detailed sequence of steps like:

3 = 1 + 2
6 = 3 + 3
10 = 6 + 4
15 = 10 + 5

You could put this in code directly for a specific sum, but if n is general, we need a loop, and hence we must see a pattern in code that we can repeat.

In each calculation the second term in the additions is a successive integer, that we can generate. Starting in the second line, the first number in each addition is the sum from the previous line. Of course the next integer and the next partial sum change from step to step, so in order to use the same code over and over we will need changeable variables, with names. We can make the partial sum be sum and we can call the next integer i. Each addition can be in the form:

sum + i

We need to remember that result, the new sum. You might first think to introduce such a name:

newSum = sum + i;

This will work. We can go through the while loop rubric:

The variables are sum, newSum and i.

To evaluate

newSum = sum + i;

the first time in the loop, we need initial values for sum and i. Our concrete example leads the way:

int sum = 1, i = 2;

We need a while loop heading with a continuation condition. How long do we want to add the next i? That is for all the value up to and including n:

while (i <= n) {

There is one more important piece - making sure the same code

newSum = sum + i;

works for the next time through the loop. We have dealt before with the idea of the next number in sequence:

i = i + 1;

What about sum? What was the newSum on one time through the loop becomes the old or just plain sum the next time through, so we can make an assignment:

sum = newSum:

All together we calculate the sum with:

int sum = 1, i = 2;
while (i <= n) {
   int newSum = sum + i;
   sum = newSum:
   i = i + 1;
}

This exactly follows our general rubric, with preparation for the next time through the loop at the end of the loop. We can condense it in this case: Since newSum is only used once, we can do away with this extra variable name, and directly change the value of sum:

int sum = 1, i = 2;
while (i <= n) {
   sum = sum + i;
   i = i + 1;
}

Finally this was supposed to fit in a function. The ultimate purpose was to return the sum, which is the final value of the variable sum, so the whole function is:

/// Return the sum of the numbers from 1 through n.
static int SumToN(int n)     // line 1
{
   int sum = 1, i = 2;       // 2
   while (i <= n) {          // 3
      sum = sum + i;         // 4
      i = i + 1;             // 5
   }
   return sum;               // 6
}

The comment before the function definition does not give a clear idea of the range of possible values for n. How small makes sense for the comment? What actually works in the function? The smallest expression starting with 1 would just be 1: (n is 1). Does that work in the function? You were probably not thinking of that when developing the function! Now look back now at this edge case. You can play computer on the code or directly test it. In this case the initialization of sum is 1, and the body of the loop never runs (2 <= 1 is false). The function execution jumps right to the return statement, and does return 1, and everything is fine.

Also you should check the program in a more general situation, say with n being 4. You should be able to play computer and generate this table, using the line numbers shown in comments at the end of lines, and following one statement of execution at a time. We only make entries where variables change value.

Line i sum Comment
1     assume 4 is passed for n
2 2 1  
3     2<=4: true, enter loop
4   3 1+2=3
5 3   2+1=3, bottom of loop
3     3<=4: true
4   6 3+3=6
5 4   3+1=4, bottom of loop
3     4<=4: true
4   10 6+4=10
5 5   4+1=5, bottom of loop
3     5<=4: false, skip loop
6     return 10

The return only happens once, so it is not in the loop. You get a value for a sum each time through, but not the final one. A common beginner error is to put the return statement inside the loop, like

static int SumToN(int n)  // 1   BAD VERSION!!!
{
   int sum = 1, i = 2;    // 2
   while (i <= n) {       // 3
      sum = sum + i;      // 4
      i = i + 1;          // 5
      return sum;         // 6  WRONG!
   }
}

Recall that when a return statement is reached, function execution ends, no matter what comes next in the code. (This is a way to break out of a while loop that we will find useful later.) In this case however, it is not what we want at all. The first sum is calculated in line 4, so sum becomes 2 + 1, but when you get to line 6, the function terminates and never loops back, returning 3.

Now about large n....

With loops we can make programs run for a long time. The time taken becomes an issue. In this case we go though the loop n-1 times, so the total time is approximately proportional to n. We write that the time is O(n), spoken “oh of n”, or “big oh of n” or “order of n”.

Computers are pretty fast, so you can try the testing program sum_to_n_test/sum_to_n_test.cs and it will go by so fast, that you will hardly notice. Try these specific numbers in tests: 5, 6, 1000, 10000, 98765. All look OK? Now try 66000. On many systems you will get quite a surprise! This is the first place we have to deal with the limited size of the int type. On many systems the limit is a bit over 2 billion. You can check out the size of int.MaxValue in csharp. The answer for 66000, and also 98765, is bigger than the upper limit. Luckily the obviously wrong negative answer for 66000 pops out at you. Did you guess before you saw the answer for 66000, that there was an issue for 98765? It is a good thing that no safety component in a big bridge was being calculated! It is a big deal that the system fails silently in such situations. Think how large the data may be that you deal with!

Now look at and run sum_to_n_long/sum_to_n_long.cs. The sum is a long integer here. Check out in csharp how big a long can be (long.MaxValue). This version of the program works for 100000 and for 98765. We can get correct answers for things that will take perceptible time. Try working up to 1 billion (1000000000, nine 0’s). It takes a while: O(n) can be slow!

By hand it is a lot slower, unless you totally change the algorithm: There is a classic story about how a calculation like this was done in grade school (n=100) by the famous mathematician Gauss. His teacher was trying to keep him busy. Gauss discovered the general, exact, mathematical formula:

1 + 2 + 3 + ... + n = n(n+1)/2.

That is the number of terms (n), times the average term (n+1)/2.

Our loop was instructive, but not the fastest approach. The simple exact formula takes about the same time for any n. (That is as long as the result fits in a standard type of computer integer!) This is basically constant time. In discussing how the speed relates to the size of n, we say it is O(1). The point is here that 1 is a constant. The time is of constant order.

We can write a ridiculously short function following Gauss’s model. Here we introduce the variable average, as in the motivation for Gauss’s answer:

/// Return the sum of the numbers from 1 through n.
static long SumToN(int n)  //CHANGED:  quick and WRONG
{
   int average = (n+1)/2;    //from Gausse's motivation
   return n*average;
}

Run the example program containing it: sum_to_n_long_bad/sum_to_n_long_bad.cs.

Test it with 5, and then try 6. ???

“Ridiculously short” does not imply correct! The problem goes back to the fact that Gauss was in math class and you are doing Computer Science. Think of a subtle difference that might come in here: Though (n+1)/2 is fine as math, recall the division operator does not always give correct answers in C#. You get an integer answer from the integer (or long) operands. Of course the exact mathematical final answer is an integer when adding integers, but splitting it according to Gauss’s motivation can put a mathematical non-integer in the middle.

The C# fix: The final answer is clearly an integer, so if we do the division last, when we know the answer will be an integer (assuming a long integer), things should be better:

long sum = n*(n+1)/2;
return sum;

Here is a shot at the whole function:

/// Return the sum of the numbers from 1 through n.
static long SumToN(int n)  //CHANGED:  quick and still WRONG
{
   long sum = n*(n+1)/2;  // final division will produce an integer
   return sum;
}

Run the example program containing it: sum_to_n_long_bad2/sum_to_n_long_bad2.cs.

Test it with 5, and then try 6. Ok so far, but go on to long integer range: try 66000 that messed us up before. ??? You get an answer that is not a multiple of 1000: not what we got before! What other issues do we have between math and C#?

Further analysis: To make sure the function always worked, it made sense to leave the parameter n an int. The function would not work with n as the largest long. The result can still be big enough to only fit in a long, so the return value is a long. All this is reasonable but the C# result is still wrong! Look deeper. While the result of n*(n+1)/2 is assigned to a long variable, the calculation n*(n+1)/2 is done with ints not mathematical integers. By the same general type rule that led to the (n+1)/2 error earlier, these operations on ints produce an int result, even when wrong.

We need to force the calculation to produce a long. In the correct looping version sum was a long, and that forced all the later arithmetic to be with longs. Here are two variations that work:

long nLong = n;
return nLong*(nLong+1)/2;

or we can avoid a new variable name by Casting to long, converting the first (left) operand to long, so all the later left-to-right operations are forced to be long:

return (long)n*(n+1)/2;

You can try example sum_to_n_long_quick/sum_to_n_long_quick.cs to finally get a result that is dependably fast and correct.

Important lessons from this humble summation problem:

  • Working and being efficient are two different things in general.
  • Math operations and C# operations are not always the same. Knowing this in theory is not the same as remembering it in practice!

Further special syntax that only makes sense in any kind of loop is discussed in Break and Continue, after we introduce the last kind of loop.