UNIT 4
Iteration
IN THIS UNIT
Summary: Iteration causes statements in your program to be repeated more than once. The two common iterative structures are the for loop and the while loop. Iteration is a fundamental programming structure and is used to solve many common tasks.
Key Ideas
Looping structures allow you to repeat instructions many times.
A for loop is used to repeat one or more instructions a specific number of times.
A while loop is used when you don’t know how many times you need to repeat a set of instructions but you know that you want to stop when some condition is met.
Variables declared within a loop are only known within the loop.
An infinite loop is a loop that does not end.
A boundary error occurs when you don’t execute a loop the correct number of times.
Introduction
So far each statement in our program has been executed at most one time. There are many situations where we will need to repeat a statement (or several statements) more than once. Repeating a statement more than once is known as iteration. Iteration changes the flow of control by repeating a set of statements zero or more times until a condition is met. There are two types of iterative structures that you need to know for the AP Computer Science A Exam: the while loop and the for loop.
Looping Statements
The for Loop
Suppose your very strict music teacher catches you chewing gum in class and tells you to write out “I will not chew gum while playing the flute” 100 times. You decide to use your computer to do the work for you. How can you write a program to repeat something as many times as you want? The answer is a loop. A for loop is used when you know ahead of time how many times you want to do a set of instructions. In this case, we know we want to write the phrase 100 times.
General Form for Creating a for Loop
The for loop uses a loop control variable to repeat its instructions. This loop control variable is typically an int and is allowed to have a one-letter name like i, j, k, and so on. This breaks the rule of having meaningful variable names. Yes, the loop control variable is a rebel.
Explanation 1: The for loop for those who like to read paragraphs . . .
When a for loop starts, its loop control variable is declared and initialized. Then, a comparison is made using the loop control variable. If the result of the comparison is true, the instructions that are to be repeated are executed one time. The loop control variable is then modified in some way (usually incremented or decremented, but not always). Next, the loop control variable is compared again using the same comparison as before. If the result of this comparison is true, the loop performs another iteration. The loop control variable is again modified (in the same way that it was before), and this process continues until the comparison of the loop control variable is false. When this happens, the loop ends and we exit (or terminate) the loop. The total number of times that the loop repeats the instructions is called the number of iterations.
Explanation 2: The for loop for those who like a list of steps . . .
Step 1: Declare and initialize the loop control variable.
Step 2: Compare the loop control variable in some way.
Step 3: If the result of the comparison is true, then execute the instructions one time.
If the result of the comparison is false, then skip to Step 6.
Step 4: Modify the loop control variable in some way (usually increment or decrement, but not always).
Step 5: Go to Step 2.
Step 6: Exit the loop and move on to the next line of code in the program.
Explanation 3: The for loop for those who like pictures . . .
The Loop Control Variable
The most common approach when using a for loop is to declare the loop control variable in the for loop. If this is the case, then the loop control variable is only known inside the for loop. Any attempt to use the loop control variable in an instruction after the loop will get a compile-time error (cannot be resolved to a variable).
However, it is possible to declare a loop control variable prior to the for loop code. If this is the case, then the loop control variable is known before the loop, during the loop, and after the loop.
Example 1
A simple example of a for loop:
Example 2
The loop control variable is often used inside the loop as shown here:
Example 3
In this example, an error occurs when an attempt is made to print the loop control variable after the loop has finished. The variable was declared inside the loop and is not known after the loop exits:
Example 4
In this example, the loop control variable is declared in a separate instruction before the loop. This allows the variable to be known before, during, and after the loop:
Fun Fact: In an early programming language called Fortran, the letters i, j, and k were reserved for storing integers. To this day, programmers still use these letters for integer variables even though they can be used to store other data types.
The Nested for Loop
A for loop that is inside of another for loop is called a nested for loop. The outer loop control variable (OLCV) is used to control the outside loop. The inner loop control variable (ILCV) is used to control the inside loop. There is no limit to the number of times you can nest a series of for loops.
General Form for a Nested for Loop
Execution Count Within a Nested for Loop
When a nested for loop is executed, the inner loop is performed in its entirety for every iteration of the outer loop. That means that the number of times that the instructions inside the inner loop are performed is equal to the product of the number of times the outer loop is performed and the number of times the inner loop is performed.
Example
To demonstrate execution count for a nested for loop: The outer loop repeats a total of three times (once for i = 0, then for i = 1, and then for i = 2). The inner loop repeats four times (once for j = 1, then for j = 2, then for j = 3, and then for j = 4). The inner loop repeats (starts over) for every iteration of the outer loop. Therefore, the System.out. println statement executes a total of 12 times:
Execution Count for a Nested for Loop
To find the total number of times that the code inside the inner for loop is executed, multiply the number of iterations of the outer loop by the number of iterations of the inner loop.
The while Loop
Consider the software that is used to check out customers at a store. The clerk drags each item over the scanner until there aren’t any more items to be scanned. Viewing this through the eyes of a programmer, I can suggest that a while loop is used to determine the final cost of all the items. The process repeats until there aren’t any more items. Now, in contrast, if the clerk asked you how many items you had in your cart before he started scanning, then I would suggest that a for loop is being used to determine the final cost of all the items.
General Form for a while Loop
Recommended form: Repeat instructions (using curly braces):
The while loop repeats instructions just like the for loop, but it does it differently. Instead of having a loop control variable that is a number like the for loop, the while loop can use any kind of data type to control when it is to perform another iteration of the loop. I like to use the phrase as long as as a replacement for the word while when reading a while loop. In other words: As long as the condition is true, I will continue to repeat the instructions. It should be noted that a for loop can be rewritten into an equivalent while loop, and vice versa (but not as easily, so it isn’t recommended). If the Boolean expression in the condition evaluates to false initially, then the loop body is not executed at all.
Explanation 1: The while loop for those who like to read paragraphs . . .
Declare and initialize some variable of any data type before the loop begins. Then compare this variable at the start of the loop. If the result of the comparison is true, the instructions inside the loop get executed one time. Then, modify the variable in some way. Next, compare the variable again in the same way as before. If the result is true, the instructions get executed one more time. This process continues until the result of the comparison is false. At this point, the loop ends and we exit the loop. You must make certain that the variable that is being compared is changed inside of the loop. If you forget to modify this variable, you may end up with a loop that never ends!
Explanation 2: The while loop for those who like a list of steps . . .
Step 1: Declare and initialize some variable of any data type.
Step 2: Compare this variable in some way.
Step 3: If the result of the comparison is true, then execute the instructions one time.
If the result of the comparison is false, then skip to Step 6.
Step 4: Modify the variable that is to be compared.
Step 5: Go to Step 2.
Step 6: Exit the loop and move on to the next line of code in the program.
Example 1
A simple example of a while loop:
Example 2
Use a while loop to require a user to enter the secret passcode for a vault that contains a million dollars. Do not allow the user to exit the loop until they get it right. If they get it right the first time, do not enter the loop (do not execute any of the instructions inside the loop).
A Flag in Programming
A flag in programming is a virtual way to signal that something has happened. Think of it as, “I’m waving a flag” to tell you that something important just occurred. Normally, boolean variables are chosen for flags. They are originally set to false, then when something exciting happens, they are set to true.
Example 3
Use a while loop to continue playing a game as long as the game is not over:
Strength of the while Loop
A strength of the while loop is that you don’t have to know how many times you will execute the instructions before you begin looping. You just have to know when you want it to end.
The Infinite Loop
If you make a mistake in a looping statement such that the loop never ends, the result is an infinite loop. You have to make sure that at some point in the loop body there is a change being made to the Boolean expression to make it false; otherwise, it will always be true and the loop will never end.
A loop must always have an “ITCH”: Initialized variable, Tested variable, and CHanged variable.
Example 1
Accidentally getting an infinite loop when using a for loop:
Example 2
Accidentally getting an infinite loop when using a while loop:
Boundary Testing
A very common error when using a for loop or a while loop is called a boundary error. It means that you accidently went one number past or one number short of the right amount. This is known as an “off by one” error, or “obo.” The loop didn’t perform the precise number of iterations. This concept is tested many times on the AP Computer Science A Exam. The only real way to prevent it is to hand-trace your code very carefully to make sure that your loop is executing the correct number of times.
Goldilocks and the Three Looping Structures
Always test that your for loops, nested for loops, and while loops are executing the correct number of times—not too many, but not too few. Just the right number of times. Hint: If you use:
then the loop will execute maximum number of times.
Standard Algorithms
Let’s take a look at some common tasks that can be done using loops that you might see on the AP Computer Science A Exam. But the tasks shown here are not the only things that you might see on the exam. You are expected to be able to read and/or write any task that involves anything that you have learned so far such as variables, conditionals, and loops for the exam.
Example 1: Find all the factors of an integer.
Example 2: Find the sum of all of the digits in an integer.
Example 3: Find the largest value in a group of numbers.
Example 4: Find the mean test score in a class of 25 students.
Example 5: Count the number of spaces that are in a string.
Example 6: Count the number of punctuation marks in a sentence.
Example 7: Reverse the order of the characters in a string.
〉 Rapid Review
Programming Statements
• Curly braces come in pairs and the code they contain is called a block of code.
• Curly braces need to be used when more than one instruction is to be executed for for and while statements.
• The scope of a variable refers to the code that knows that the variable exists.
• Variables declared within a loop are only known within that loop.
• The for loop is used to repeat one or more instructions a specific number of times.
• The for loop is a good choice when you know exactly how many times you want to repeat a set of instructions.
• The for loop uses a numeric loop control variable that is compared and also modified during the execution of the loop. When the comparison that includes this variable evaluates to false, the loop exits.
• Variables declared within a for loop are only known within that for loop.
• A nested for loop is a for loop inside of a for loop.
• The number of iterations of a nested for loop is the product of the number of iterations for each loop.
• The while loop does not require a numeric loop control variable.
• The while statement must contain a conditional that compares a variable that is modified inside the loop.
• Choose a while loop when you don’t know how many times you need to repeat a set of instructions but know that you want to stop when some condition is met.
• An infinite loop is a loop that never ends.
• Forgetting to modify the loop control variable or having a condition that will never be satisfied are typical ways to cause infinite loops.
• Variables declared within a while loop are only known within the while loop.
• A boundary error occurs when you don’t execute a loop the correct number of times.
〉 Review Questions
Basic Level
1. Consider the following code segment.
What is printed as a result of executing the code segment?
(A) 4
(B) 9
(C) 10
(D) 13
(E) 31
2. Consider the following code segment.
What is printed as a result of executing the code segment?
(A) 5
(B) 7
(C) 9
(D) 13
(E) 20
3. Consider the following code segment.
What is printed as a result of executing the code segment?
(A) -1 0 2 5
(B) -1 0 3 7
(C) -1 1 4 8
(D) 0 2 5 9
(E) 0 1 3 7
4. Which of the following code segments will print exactly eight "$" symbols?
I. 
II. 
III. 
(A) I only
(B) II only
(C) I and II only
(D) I and III only
(E) I, II, and III
5. Consider the following code segment.
Which of the following should replace /* missing condition */ to ensure that a + b will not be too large to be held correctly in result?
(A) a + b < Integer.MAX _ VALUE
(B) a + b <= Integer.MAX _ VALUE
(C) Integer.MIN _ VALUE + a <= b
(D) Integer.MAX _ VALUE – a <= b
(E) Integer.MAX _ VALUE – a >= b
Advanced Level
6. Consider the following code segment.
How many "*" symbols are printed as a result of executing the code segment?
(A) 5
(B) 10
(C) 45
(D) 55
(E) 100
7. Consider the following code segment.
What is printed as a result of executing the code segment?
(A) 3
(B) 4
(C) 6
(D) 7
(E) Nothing will be printed; infinite loop.
8. Which of the following three code segments will produce the same output?
I. 
II. 
III. 
(A) I and II only
(B) II and III only
(C) I and III only
(D) I, II, and III
(E) All three outputs are different.
9. Consider the following code segment.
What is printed as a result of executing the code segment?
(A) 0.0
(B) -4.0
(C) 5
(D) The program will end successfully, but nothing will be printed.
(E) Nothing will be printed. Run-time error: ArithmeticException.
10. Consider the following code segment.
What is printed as a result of executing the code segment?
(A) 0 3 2 1 0 0 3
(B) 0 0 3 2 2 1
(C) 0 3 2 1 0 0
(D) 0 0 3 2 2 1 0
(E) Many numbers will be printed; infinite loop.
11. Consider the following code segment.
What is printed as a result of executing the code segment?
(A) 20.0
(B) 6.0
(C) 19.0
(D) 9.0
(E) -40.0
〉 Answers and Explanations
Bullets mark each step in the process of arriving at the correct solution.
1. The answer is B.
• The first time we evaluate the while condition, value = 31, which is >= 10, so the loop executes.
• In the loop, we subtract count from value which becomes 30,
• and then we add 3 to count, which becomes 4.
• Then we go back to the top of the while loop and reevaluate the condition. 30 >= 10, so we execute the loop again.
• This time we subtract 4 from value, since count is now 4. value = 26
• and count = 7.
• Back up to the top, 26 >= 10, so on we go.
• value = 27 - 7 = 19 and count = 10.
• Since 10 >= 10, we will execute the loop one more time.
• value = 19 - 10 = 9 and count = 13.
• This time when we evaluate the condition, it is no longer true, so we exit the loop and print value, which equals 9.
2. The answer is D.
• When we first enter the for loop count = 5 and i = 3.
• The first time through the loop, we execute count += i, which makes count = 8, and we increment i by 2, which makes i = 5.
• i < 7, so we execute the loop again; count = 8 + 5 = 13, and i = i + 2 = 7.
• This time the condition i < 7 fails and we exit the loop. 13 is printed.
3. The answer is A.
• The first time through the loop, incr = 1 and i = 0. 0 - 1 = -1, which is printed; then incr is increased to 2. The increment portion of this for loop is a little unusual. Instead of i++ or i = i + 2, it’s i = i + incr, so, since incr = 2 and i = 0, i becomes 2.
• 2 < 10 so we continue. 2 - 2 = 0, which is printed, incr = 3 and i = 2 + 3 = 5.
• 5 < 10 so we continue. 5 - 3 = 2, which is printed, incr = 4 and i = 5 + 4 = 9.
• 9 < 10 so we continue. 9 - 4 = 5, which is printed, incr = 5 and i = 9 + 5 = 14.
• This time we fail the condition, so our loop ends having printed -1 0 2 5
4. The answer is E.
• The first option is the classic way to write a for loop. If you always start at i = 0 and go until i < n, you know the loop will execute n times without having to think about it (using i++ of course). So this first example prints eight "$".
• The second example is the exact same loop as the first example, except written as a while loop instead of a for loop. You can see the i = 0, the i < 8, and the i++. So this example also prints eight "$".
• The third example shows why we always stick to the convention used in the first example. Here we have to reason it out: i will equal 7, 10, 13, 16, 19, 22, 25, 28 before finally failing at 31. That’s eight different values, which means eight times through the loop. So this example also prints eight "$".
5. The answer is E.
• Integer.MAX _ VALUE is a constant that represents the greatest value that can be stored in an int. In this problem, we need to make sure that a + b is not greater than that value.
• Solution b seems like the logical way to do this, but if a + b is too big to fit in an int, then we can’t successfully add them together to test if they are too big. a + b will overflow.
• We need to do some basic algebra and subtract a from both sides giving us:
• The left and right sides of the expression have been switched, so we need to flip the inequality. Flipping the < gives us >=.
6. The answer is D.
• The outer loop is going to execute 10 times: j = 0 through j = 9.
• The inner loop is trickier. The number of times it executes depends on j.
• The first time through, j = 0, so k = 10, 9, 8 . . . 1 (10 times).
• The second time through, j = 1, so k = 10, 9, 8 . . . 2 (9 times).
• The third time through, j = 2, so k = 10, 9, 8 . . . 3 (8 times).
• There’s a clear pattern here, so we don’t need to write them all out. We do have to be careful that we stop at the right time though.
• The last time through the loop, j = 9, so k = 10 (1 time).
• Adding it all together: 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55
7. The answer is A.
• b1 and b2 are both true. The OR ( || ) in the while condition requires that at least one of them be true, so we enter the loop for the first time.
• 7 > 4 so we execute b2 = ! b2. That’s a tricky little statement that is used to flip the value of a boolean. Since b2 is true, !b2 is false, and we assign that value back into b2, which becomes false.
• We skip the else clause and subtract one from x.
• At the bottom of the loop: b1 = true, b2 = false, x = 6.
• The while condition now evaluates to (true || false), which is still true, so we execute the loop.
• 6 > 4 so we flip b2 again. b2 is now true.
• Skip the else clause, subtract one from x.
• At the bottom of the loop: b1 = true, b2 = true, x = 5.
• The while condition now evaluates to (true || true), which is true, so we execute the loop.
• 5 > 4 so we flip b2 again. b2 is now false.
• Skip the else clause, subtract one from x.
• At the bottom of the loop: b1 = true, b2 = false, x = 4.
• The while condition now evaluates to (true || false), which is still true, so we execute the loop.
• This time the if condition is false, so we execute the else clause, which flips the condition of b1 instead of b2. b1 is now false.
• Subtract one from x.
• At the bottom of the loop: b1 = false, b2 = false, x = 3.
• Now when we go to evaluate the while condition, we have (false || false). Do not execute the loop. Print the value of x, which is 3.
8. The answer is C.
• Option I
• As we enter the loop for the first time, i = 1, and that’s what gets printed. Then we multiply by 2, i = 2.
• We print 2, multiply by 2, i = 4.
• We print 4, multiply by 2, i = 8.
• We print 8, multiply by 2, i = 16, which fails the loop condition so we exit the loop.
• Final output: 1 2 4 8
• Option II
• We can see by examining the for loop that we will execute the loop 4 times: i = 4, 3, 2, 1.
• Each time through the loop we will print (4 - i ) * 2 + 1.
• (4 - 4) * 2 + 1 = 1
• (4 - 3) * 2 + 1 = 3
• (4 - 2) * 2 + 1 = 5
• (4 - 1) * 2 + 1 = 7
• Final output: 1 3 5 7
• Option III
• We can see by examining the for loop that we will execute the loop 4 times: i = 0, 1, 2, 3.
• Each time through the loop we will print (int)Math.pow(2, i). (Math.pow returns a double, so we cast to an int before printing.)
• 20 = 1
• 21 = 2
• 22 = 4
• 23 = 8
• Final output: 1 2 4 8
• Options I and III have the same output.
9. The answer is A.
• The first time through the loop: count = 6.0 and num = 0.
• Looking at the if condition: 6.0 != 0, but 0 / 6 is 0 
false, so we skip the if clause and go back to the start of the loop.
• Back to the top of the loop: count is still 6.0, but num = 1.
• Looking at the if condition: 6.0 ! = 0 && 1 / 6.0 > 0 true, so we execute the if clause and count = 6.0 - 1 = 5.0.
• Back to the top of the loop: count = 5.0 and num = 2.
• Looking at the if condition: 5.0 ! = 0 && 1 / 5.0 > 0 true, so we execute the if clause and count = 5.0 - 2 = 3.0.
• Back to the top of the loop: count = 3.0 and num = 3.
• Looking at the if condition: 3.0 ! = 0 && 3 / 3.0 > 0 true, so we execute the if clause and count = 3.0 - 3 = 0.0.
• Back to the top of the loop: count = 0.0 and num = 4.
• Looking at the if condition: Here’s where it gets interesting. If we execute 4 / 0.0, we are going to crash our program with an ArithmeticExceptionError, but that’s not going to happen. The first part of the condition, count != 0 is false, and Java knows that false AND anything is false, so it doesn’t even bother to execute the second part of the condition. That is called short-circuiting, and it is often used for exactly this purpose. The condition is false; the if clause doesn’t get executed.
• Back to the top of the loop: count = 0.0 and num = 5, so our loop is complete and we print the value of count, which is 0.0.
10. The answer is A.
• The only thing we can do is to trace the code carefully line by line until we have the answer.
• n = 0. Print 0 % 4, which is 0
• 0 % 5 = 0 so we execute the else, now n = 3.
• Print 3 % 4, which is 3
• 3 % 5 = 3 so we execute the else, now n = 6.
• Print 6 % 4, which is 2
• 6 % 5 = 1 so we execute the else, now n = 9.
• Print 9 % 4, which is 1
• 9 % 5 = 1 so we execute the else, now n = 12.
• Print 12 % 4, which is 0
• 12 % 5 = 2 so finally we execute the if, now n = 16.
• Print 16 % 4, which is 0
• 16 % 5 = 1 so we execute the else, now n = 19.
• Print 19 % 4, which is 3
• 19 % 5 is 4 so we execute the else, now n = 22, which completes the loop.
• We have printed: 0 3 2 1 0 0 3
11. The answer is D.
• When we enter the loop, tabulate = 100 and repeat = 1
• tabulate = 100 - Math.pow(1, 2) = 99; increment repeat to 2
• 99 > 20 so we enter the loop again
• tabulate = 99 - Math.pow(2, 2) = 95; increment repeat to 3
• 95 > 20
• tabulate = 95 - Math.pow(3, 2) = 86; increment repeat to 4
• 86 > 20
• tabulate = 86 - Math.pow(4, 2) = 70; increment repeat to 5
• 70 > 20
• tabulate = 70 - Math.pow(5, 2) = 45; increment repeat to 6
• 45 > 20
• tabulate = 45 - Math.pow(6, 2) = 9; increment repeat to 7
• 9 < 20 so we exit the loop and print 9