AP COMPUTER SCIENCE PRINCIPLES • ALGORITHMS AND PROGRAMMING

Iteration

Repeating instructions efficiently transforms how algorithms process data and solve complex problems at scale.

SECTION 1

Historical Context & Motivation

Long before modern programming languages existed, mathematicians and engineers recognized that many computational tasks require performing the same operation repeatedly. Iteration—the process of repeating a sequence of instructions—emerged as a foundational concept when Charles Babbage designed mechanical computing engines in the 1830s. His collaborator, Ada Lovelace, wrote what is widely considered the first algorithm, which included an iterative loop to compute Bernoulli numbers. The idea that a machine could cycle through the same set of instructions, modifying values with each pass, was a profound intellectual leap that distinguished computation from mere calculation.

1837

Babbage's Analytical Engine

Charles Babbage designs the Analytical Engine with a "mill" capable of looping through instruction cards, introducing mechanical iteration.

1843

Lovelace's Algorithm

Ada Lovelace publishes an algorithm for computing Bernoulli numbers that features an explicit iterative loop—often cited as the first computer program.

1936

Turing Machines

Alan Turing formalizes computation with the Turing machine, where iteration is captured by the machine's ability to revisit states while scanning a tape.

1957

FORTRAN's DO Loop

IBM releases FORTRAN, the first high-level language, featuring the DO loop construct that makes iteration accessible to scientists and engineers.

2000s

Modern Iteration Patterns

Languages like Python popularize for-each loops and list comprehensions, making iteration over collections concise and expressive.

The central question that iteration answers is deceptively simple: how can a computer execute the same instructions many times without the programmer writing them out individually? Without iteration, processing a list of 10,000 students' grades would require 10,000 separate lines of code. With iteration, a handful of lines suffice. This principle is so fundamental that every general-purpose programming language provides loop constructs, and the AP Computer Science Principles exam tests your ability to trace, write, and reason about iterative algorithms.

SECTION 2

Core Principles & Definitions

At its core, iteration means executing a block of code multiple times. The AP CSP exam uses a pseudocode language where loops are expressed with REPEAT n TIMES and REPEAT UNTIL(condition) constructs. Understanding the mechanics behind these constructs—when the loop body executes, how the condition is evaluated, and what happens when the loop terminates—is essential for both the exam and real-world programming.

Loop Body

The block of statements inside the loop that execute on each pass. Every iteration runs the body exactly once before checking whether to continue.

Loop Condition

A Boolean expression evaluated before (or after) each iteration. In REPEAT UNTIL, the loop continues while the condition is false and stops when it becomes true.

Iteration Variable

A variable (often called i or index) that changes with each pass through the loop, tracking progress and often controlling termination.

Termination

A well-designed loop must eventually stop. If the condition never becomes true (or the counter never reaches its target), the result is an infinite loop—a common bug.

Accumulation Pattern

A variable initialized before the loop and updated inside it to collect results—summing values, building strings, or counting occurrences across iterations.

✦ KEY TAKEAWAY

Think of iteration like an assembly line in a factory. Each product (data element) passes through the same set of stations (loop body) in sequence. The line keeps running until every product is processed or a quality inspector (loop condition) signals a stop. Without the assembly line, a worker would have to carry each product through every station individually—possible for three products, impractical for three million.

SECTION 3

Visual Explanation

The flowchart traces a REPEAT UNTIL(i > 5) loop that sums integers 1 through 5. The diamond checks the condition; if false, execution flows down through the loop body (cyan boxes), then loops back (dashed violet arrow) to re-evaluate. The trace table at bottom shows how sum accumulates to 15 over five passes.

The flowchart above illustrates the control flow of a condition-controlled loop. Notice three critical features: the initialization step before the loop sets starting values, the condition diamond is evaluated at the top of each pass (in the AP pseudocode, REPEAT UNTIL checks at the start), and the loop body must modify a variable that eventually makes the condition true. If the body never changed i, the loop would never terminate. The trace table is a powerful exam technique—manually tracking variable values through each iteration catches off-by-one errors and confirms your understanding of the algorithm's behavior.

SECTION 4

How Iteration Works in AP Pseudocode

Count-Controlled Loops

The simplest form of iteration is the count-controlled loop, written in AP pseudocode as REPEAT n TIMES. The value n is evaluated once when the loop begins, and the body executes exactly n times. This construct is ideal when you know in advance how many repetitions are needed—for example, moving a robot forward 5 squares or drawing 10 sides of a polygon.

COUNT-CONTROLLED LOOP

REPEAT n TIMES { <body> }

The body executes exactly n times. If n ≤ 0, the body never executes.

Condition-Controlled Loops

When the number of iterations is not known ahead of time, the condition-controlled loop REPEAT UNTIL(condition) is used. The condition is a Boolean expression checked before each iteration. The loop body executes while the condition is false and terminates as soon as it becomes true. This is the inverse of a typical while loop in languages like Python or Java, which runs while the condition is true. Confusing this polarity is one of the most common exam errors.

CONDITION-CONTROLLED LOOP

REPEAT UNTIL(condition) { <body> }

The body executes repeatedly while condition is false. Once condition evaluates to true, execution moves past the loop.

Iterating Over Lists

The AP pseudocode also supports iterating through each element of a list using FOR EACH item IN list. On each pass, the variable item takes the value of the next element in the list, proceeding from the first element to the last. This construct is especially useful for searching, filtering, or transforming list data. Unlike REPEAT UNTIL, the loop automatically terminates when all elements have been visited, so infinite loops are impossible with this construct alone.

LIST ITERATION

FOR EACH item IN list { <body> }

On each pass, item is assigned the next element of list in order. The body executes LENGTH(list) times.

SECTION 5

Common Iteration Patterns

On the AP CSP exam, iteration almost always appears in combination with one of several standard algorithmic patterns. Recognizing these patterns lets you quickly identify what a given loop is doing, which is essential for the multiple-choice section where you must trace code under time pressure. The diagram below classifies the four most common patterns tested on the exam.

Four iteration patterns commonly tested on the AP CSP exam. Accumulation collects a running total. Linear search checks each element for a match. Filtering builds a new list of qualifying elements. Find min/max tracks the most extreme value seen so far.

Each pattern shares a common structure: an initialization step before the loop, a loop body that conditionally updates a variable, and a final result available after termination. The accumulation pattern initializes a running total (often to 0) and adds to it each pass. Linear search initializes a Boolean flag to false and sets it to true upon finding a match. Filtering initializes an empty list and appends qualifying elements. Find min/max initializes to the first element and replaces when a more extreme value is found. Mastering these four patterns covers the vast majority of iteration questions on the exam.

SECTION 6

Worked Example

Let us trace through a complete algorithm that uses iteration to find the maximum value in a list. This combines the loop mechanism with the find-max pattern, and demonstrates the trace-table technique that is invaluable on exam day.

Finding the Maximum Value in a List

Step 1 — Understand the ProblemGiven scores ← [72, 85, 91, 68, 95], find and display the highest score. We will use a FOR EACH loop with the find-max pattern.

Step 2 — Write the PseudocodemaxScore ← scores[1] FOR EACH s IN scores IF (s > maxScore) maxScore ← s DISPLAY(maxScore)

Step 3 — Trace Iteration 1 (s = 72)maxScore starts at 72 (scores[1]). Is 72 > 72? No. maxScore remains 72.

maxScore = 72

Step 4 — Trace Iteration 2 (s = 85)Is 85 > 72? Yes. Update maxScore to 85.

maxScore = 85

Step 5 — Trace Iteration 3 (s = 91)Is 91 > 85? Yes. Update maxScore to 91.

maxScore = 91

Step 6 — Trace Iteration 4 (s = 68)Is 68 > 91? No. maxScore remains 91.

maxScore = 91

Step 7 — Trace Iteration 5 (s = 95)Is 95 > 91? Yes. Update maxScore to 95.

maxScore = 95

Step 8 — OutputThe loop terminates after visiting all five elements. DISPLAY outputs 95, confirming the highest score in the list.

Output: 95

SECTION 7

Comparing Loop Types

Choosing the right loop construct depends on the problem. The AP CSP exam expects you to know when each construct is most appropriate and to translate between them when needed. The table below contrasts the three loop types along several dimensions.

Comparison of AP CSP loop constructs

Feature	REPEAT n TIMES	REPEAT UNTIL	FOR EACH
When to use	Known number of repetitions	Unknown repetitions; stop on a condition	Process every element in a list
Risk of infinite loop	None	Yes, if condition never becomes true	None
Access to current element	No built-in variable	Must manage index manually	Automatic via loop variable
Can exit early	No	Yes, via condition	No (always visits all elements)
Typical exam usage	Robot movement, simple repetition	Input validation, sentinel loops	List processing, search, accumulation

✦ KEY TAKEAWAY

All three loop types are computationally equivalent—any problem solvable with one can be solved with the others, though some solutions are more elegant. REPEAT n TIMES is syntactic sugar for a REPEAT UNTIL with a counter, and FOR EACH is shorthand for indexing through a list with a counter. On the exam, choose the construct that most clearly expresses intent: if you know the count, use REPEAT n TIMES; if you are processing a list, use FOR EACH; if you need to stop on a dynamic condition, use REPEAT UNTIL.

SECTION 8

Connection to Advanced Concepts

Iteration on the AP CSP exam is one step in a broader progression. In AP Computer Science A and college data structures courses, iteration scales up to nested loops, recursion, and algorithm efficiency analysis. Understanding iteration deeply prepares you for these more advanced topics, and even on the CSP exam, questions occasionally touch on efficiency and nested iteration.

AP CSP iteration vs. advanced topics

Concept	AP CSP (This Course)	Advanced (AP CSA / College)
Basic iteration	REPEAT, REPEAT UNTIL, FOR EACH	for, while, do-while, enhanced for
Nested loops	Recognized conceptually	2D array traversal, sorting algorithms
Efficiency	Reasonable vs. unreasonable time	Big-O notation: O(n), O(n²), O(log n)
Recursion	Not tested	Recursive methods as an alternative to loops

One concept that bridges CSP and more advanced study is algorithmic efficiency. A single loop over a list of n items performs n operations, which is considered linear time. A loop nested inside another loop may perform n × n = n² operations, which is quadratic time. The CSP exam asks you to distinguish between algorithms that run in reasonable time (polynomial) and those that do not (exponential), and understanding how loops multiply operations is the key to answering these questions correctly.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Consider the following pseudocode:

x ← 10
REPEAT UNTIL(x = 0)
{
    x ← x - 3
}

What happens when this code executes? A. The loop executes 3 times and x ends at 1. B. The loop executes 4 times and x ends at -2. C. The loop runs infinitely because x never equals 0. D. The loop executes 10 times and x ends at 0.

PROBLEM 2 — BASIC CALCULATION

What value is displayed after this code executes?

nums ← [4, 7, 2, 9]
result ← 0
FOR EACH n IN nums
{
    result ← result + n
}
DISPLAY(result)

A. 9 B. 22 C. 4 D. 18

PROBLEM 3 — INTERMEDIATE

Consider the following pseudocode:

data ← [3, 8, 1, 5, 12, 4]
count ← 0
FOR EACH val IN data
{
    IF (val > 4)
    {
        count ← count + 1
    }
}
DISPLAY(count)

Select two of the following that are true about this code. A. The loop iterates exactly 6 times. B. The displayed value is 3. C. The code uses the linear search pattern. D. Changing the condition to val ≥ 4 would increase the displayed value by 3.

PROBLEM 4 — APPLIED

A teacher stores student grades in a list called grades. She wants to write an algorithm that calculates the average grade and then counts how many students scored above that average. Describe the algorithm using AP pseudocode. Your response should include: (a) Code to compute the average using iteration. (b) Code to count values above the average using a second loop. (c) An explanation of why two separate loops are necessary.

PROBLEM 5 — CRITICAL THINKING

A programmer writes the following algorithm to determine whether a list of integers is sorted in non-decreasing order:

sorted ← true
i ← 1
REPEAT UNTIL(i ≥ LENGTH(myList))
{
    IF (myList[i] > myList[i + 1])
    {
        sorted ← false
    }
    i ← i + 1
}

(a) Trace the algorithm for myList ← [2, 5, 3, 8] and state the final value of sorted. (b) Explain one inefficiency in this algorithm and describe how it could be improved. (c) If the list has n elements, how many comparisons does this algorithm make? Would nested loops change this? (d) Explain what happens if myList contains only one element.

SUMMARY

Iteration — Summary

Iteration is the process of repeating a block of code, and it is one of the most fundamental concepts in programming. The AP CSP exam tests three loop constructs: REPEAT n TIMES for a known number of repetitions, REPEAT UNTIL(condition) for condition-controlled loops that stop when a Boolean expression becomes true, and FOR EACH item IN list for processing every element of a list. Each construct includes a loop body that executes on each pass and a termination mechanism that ensures the loop eventually stops.

Four core patterns appear repeatedly on the exam: accumulation (summing or counting), linear search (finding a target), filtering (selecting a subset), and find min/max (tracking extremes). All share a common structure of initialization before the loop, conditional updates inside the body, and a result available after termination. Mastering trace tables—manually tracking variable values through each iteration—is the single most effective strategy for answering iteration questions accurately under exam conditions. Watch for infinite loops (when the termination condition is never met) and off-by-one errors (when a loop runs one too many or one too few times).

More AP Computer Science Principles Lessons

Keep learning with more lessons from the same subject.

AP COMPUTER SCIENCE PRINCIPLES • ALGORITHMS AND PROGRAMMING

Iteration

Repeating instructions efficiently transforms how algorithms process data and solve complex problems at scale.

SECTION 1

Historical Context & Motivation

1837

Babbage's Analytical Engine

Charles Babbage designs the Analytical Engine with a "mill" capable of looping through instruction cards, introducing mechanical iteration.

1843

Lovelace's Algorithm

Ada Lovelace publishes an algorithm for computing Bernoulli numbers that features an explicit iterative loop—often cited as the first computer program.

1936

Turing Machines

Alan Turing formalizes computation with the Turing machine, where iteration is captured by the machine's ability to revisit states while scanning a tape.

1957

FORTRAN's DO Loop

IBM releases FORTRAN, the first high-level language, featuring the DO loop construct that makes iteration accessible to scientists and engineers.

2000s

Modern Iteration Patterns

Languages like Python popularize for-each loops and list comprehensions, making iteration over collections concise and expressive.

SECTION 2

Core Principles & Definitions

Loop Body

The block of statements inside the loop that execute on each pass. Every iteration runs the body exactly once before checking whether to continue.

Loop Condition

A Boolean expression evaluated before (or after) each iteration. In REPEAT UNTIL, the loop continues while the condition is false and stops when it becomes true.

Iteration Variable

A variable (often called i or index) that changes with each pass through the loop, tracking progress and often controlling termination.

Termination

A well-designed loop must eventually stop. If the condition never becomes true (or the counter never reaches its target), the result is an infinite loop—a common bug.

Accumulation Pattern

A variable initialized before the loop and updated inside it to collect results—summing values, building strings, or counting occurrences across iterations.

✦ KEY TAKEAWAY

SECTION 3

Visual Explanation

SECTION 4

How Iteration Works in AP Pseudocode

Count-Controlled Loops

COUNT-CONTROLLED LOOP

REPEAT n TIMES { <body> }

The body executes exactly n times. If n ≤ 0, the body never executes.

Condition-Controlled Loops

CONDITION-CONTROLLED LOOP

REPEAT UNTIL(condition) { <body> }

The body executes repeatedly while condition is false. Once condition evaluates to true, execution moves past the loop.

Iterating Over Lists

LIST ITERATION

FOR EACH item IN list { <body> }

On each pass, item is assigned the next element of list in order. The body executes LENGTH(list) times.

SECTION 5

Common Iteration Patterns

SECTION 6

Worked Example

Finding the Maximum Value in a List

Step 1 — Understand the ProblemGiven scores ← [72, 85, 91, 68, 95], find and display the highest score. We will use a FOR EACH loop with the find-max pattern.

Step 2 — Write the PseudocodemaxScore ← scores[1] FOR EACH s IN scores IF (s > maxScore) maxScore ← s DISPLAY(maxScore)

Step 3 — Trace Iteration 1 (s = 72)maxScore starts at 72 (scores[1]). Is 72 > 72? No. maxScore remains 72.

maxScore = 72

Step 4 — Trace Iteration 2 (s = 85)Is 85 > 72? Yes. Update maxScore to 85.

maxScore = 85

Step 5 — Trace Iteration 3 (s = 91)Is 91 > 85? Yes. Update maxScore to 91.

maxScore = 91

Step 6 — Trace Iteration 4 (s = 68)Is 68 > 91? No. maxScore remains 91.

maxScore = 91

Step 7 — Trace Iteration 5 (s = 95)Is 95 > 91? Yes. Update maxScore to 95.

maxScore = 95

Step 8 — OutputThe loop terminates after visiting all five elements. DISPLAY outputs 95, confirming the highest score in the list.

Output: 95

SECTION 7

Comparing Loop Types

Comparison of AP CSP loop constructs

Feature	REPEAT n TIMES	REPEAT UNTIL	FOR EACH
When to use	Known number of repetitions	Unknown repetitions; stop on a condition	Process every element in a list
Risk of infinite loop	None	Yes, if condition never becomes true	None
Access to current element	No built-in variable	Must manage index manually	Automatic via loop variable
Can exit early	No	Yes, via condition	No (always visits all elements)
Typical exam usage	Robot movement, simple repetition	Input validation, sentinel loops	List processing, search, accumulation

✦ KEY TAKEAWAY

SECTION 8

Connection to Advanced Concepts

AP CSP iteration vs. advanced topics

Concept	AP CSP (This Course)	Advanced (AP CSA / College)
Basic iteration	REPEAT, REPEAT UNTIL, FOR EACH	for, while, do-while, enhanced for
Nested loops	Recognized conceptually	2D array traversal, sorting algorithms
Efficiency	Reasonable vs. unreasonable time	Big-O notation: O(n), O(n²), O(log n)
Recursion	Not tested	Recursive methods as an alternative to loops

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Consider the following pseudocode:

x ← 10
REPEAT UNTIL(x = 0)
{
    x ← x - 3
}

PROBLEM 2 — BASIC CALCULATION

What value is displayed after this code executes?

nums ← [4, 7, 2, 9]
result ← 0
FOR EACH n IN nums
{
    result ← result + n
}
DISPLAY(result)

A. 9 B. 22 C. 4 D. 18

PROBLEM 3 — INTERMEDIATE

Consider the following pseudocode:

data ← [3, 8, 1, 5, 12, 4]
count ← 0
FOR EACH val IN data
{
    IF (val > 4)
    {
        count ← count + 1
    }
}
DISPLAY(count)

PROBLEM 4 — APPLIED

PROBLEM 5 — CRITICAL THINKING

A programmer writes the following algorithm to determine whether a list of integers is sorted in non-decreasing order:

sorted ← true
i ← 1
REPEAT UNTIL(i ≥ LENGTH(myList))
{
    IF (myList[i] > myList[i + 1])
    {
        sorted ← false
    }
    i ← i + 1
}

SUMMARY

Iteration — Summary

More AP Computer Science Principles Lessons

Keep learning with more lessons from the same subject.