Iteration - AP Computer Science Principles Study Guide

Getting Started

Many tasks in the real world, from dealing cards to a group of players to washing a stack of dishes, involve repeating the same action over and over. Computers are exceptionally good at these repetitive jobs. To write instructions for these tasks, we need a way to tell the computer to repeat a set of steps, a process known as iteration.

What You Should Be Able to Do

• Explain the purpose of iteration within an algorithm.

• Write algorithms using both fixed and condition-controlled loops.

• Trace the execution of an algorithm that includes iteration to determine its final output.

• Differentiate between a loop that runs a set number of times and one that runs until a condition is met.

Key Concepts & Application

The Core Idea

An algorithm is a finite set of instructions to accomplish a task. By default, a computer follows these instructions one after another, in sequence. However, many problems require us to repeat a block of instructions. Iteration is the control structure that allows for this repetition, often called a "loop."

Think about a factory assembly line. One station might be instructed to tighten four bolts on every car that passes. This task is repeated for each car. This is like a fixed loop—you know exactly how many bolts to tighten. Now, imagine another station that polishes a car's hood until it shines. The worker doesn't know if it will take 10 seconds or 30 seconds; they just keep polishing until the condition "is shiny" becomes true. This is a condition-controlled loop. These two fundamental ideas form the basis of iteration in programming.

Logic & Application

Iteration changes the standard sequential flow of control in an algorithm, allowing blocks of code to be executed multiple times. There are two primary forms of iteration you will use.

1. Fixed Iteration: REPEAT n TIMES

This structure is used when you know in advance exactly how many times you need to repeat the instructions.

Annotated Pseudocode: Simple Counter

This algorithm displays a countdown from 3 to 1.

count <- 3

REPEAT 3 TIMES

{

  DISPLAY(count)

  count <- count - 1 // Decrease the value of count by 1

}

DISPLAY("Go!")

• Line 1: A variable count is initialized to 3.

• Line 2: The REPEAT 3 TIMES command starts a loop that will execute the code inside its curly braces {...} exactly three times.

• Line 4: The current value of count is displayed.

• Line 5: The value of count is updated for the next loop cycle.

2. Conditional Iteration: REPEAT UNTIL (condition)

This structure is used when you need to repeat instructions until a certain condition becomes true. The number of repetitions is not known ahead of time.

Annotated Pseudocode: Guessing Game

This algorithm asks a user for a guess until they correctly guess the secret number, which is 7.

secretNumber <- 7

userGuess <- 0 // Initialize userGuess to a value that is not 7


// The loop will continue as long as userGuess is not equal to secretNumber

REPEAT UNTIL (userGuess = secretNumber)

{

  DISPLAY("Guess the number:")

  userGuess <- INPUT() // Get a new guess from the user

}

DISPLAY("You guessed it!")

• Line 4: The REPEAT UNTIL command starts a loop. It will check the condition (userGuess = secretNumber)after each full run of the code inside the braces.

• Line 6-7: The user is prompted and their input is stored in userGuess.

• Loop Logic: If the user enters 5, the condition (5 = 7) is false, so the loop repeats. If the user enters 7, the condition (7 = 7) is true, and the loop terminates.

Tracing & Analysis

To understand how loops work, we can trace their execution step-by-step, tracking the value of variables.

Logic Trace: Summing a List

Let's trace an algorithm that calculates the sum of numbers in a list.

numbers <- [10, 20, 5]

total <- 0

i <- 1

REPEAT LENGTH(numbers) TIMES

{

total <- total + numbers[i]

i <- i + 1

}

After 3 iterations, the loop finishes. The final value of total is 35.

Key Terminology & Logic

A compact reference for the iteration structures and terms.

• Iteration: The process of repeating a block of instructions in an algorithm; a loop.

• REPEAT n TIMES { ... }: A fixed loop that executes the code block n times.

• REPEAT UNTIL (condition) { ... }: A conditional loop that executes the code block until the condition evaluates to true.

• Infinite Loop: A loop where the stopping condition is never met, causing the algorithm to run forever.

Core Concepts & Terminology

This section provides formal definitions for key concepts related to iteration.

• Algorithm: A finite, well-defined sequence of instructions used to accomplish a specific task or solve a problem.

• Iteration: A repetitive action or process within an algorithm. Iteration uses a "loop" to execute the same block of code multiple times.

• Flow of Control: The order in which individual statements, instructions, or function calls of a program are executed or evaluated. Iteration and selection are the primary means of altering the default sequential flow.

• Fixed Iteration: A loop that repeats a specific, predetermined number of times. This is also known as a count-controlled loop.

  
  // This block will run exactly 4 times.
  
  REPEAT 4 TIMES
  
  {
  
    DISPLAY("Hello")
  
  }
  

• Conditional Iteration: A loop that continues to repeat as long as a condition is false (or, until it becomes true). The number of repetitions is not predetermined.

  
  // This block will run until the user types "stop".
  
  response <- ""
  
  REPEAT UNTIL (response = "stop")
  
  {
  
    response <- INPUT()
  
  }
  

Core Skill Check

Test your understanding with these short exercises.

• Logic Tracing: What is the final value of score after this pseudocode runs?

  score <- 10; REPEAT 4 TIMES { score <- score + 5 }

• Debugging: Identify the logic error in this pseudocode that is intended to count down from 5 to 1.

  count <- 5; REPEAT UNTIL (count = 0) { DISPLAY("T-minus...") }

• Application: Describe a real-world feature of a music streaming app that clearly relies on iteration.

Common Misconceptions & Clarifications

• Confusing REPEAT UNTIL with "repeat while."

  The pseudocode REPEAT UNTIL (condition) stops when the condition is true. Some programming languages use while loops that continue as long as a condition is true. Be careful to read the logic correctly: you are repeating until something happens.

• "Off-by-One" Errors.

  A very common mistake is to loop one too many or one too few times. REPEAT 10 TIMES will execute the code block exactly ten times. When processing lists, be careful that your loop doesn't try to access an item that is out of bounds.

• Assuming a loop must use a counter variable.

  While many loops use a counter (like i), especially when processing lists, conditional loops often do not. A REPEAT UNTIL loop might depend on user input, a sensor reading, or a random event, with no counter needed.

• Believing all loops must end.

  A correctly written program should not have loops that run forever. However, it is possible to create an infinite loop by writing a REPEAT UNTIL statement where the condition can never become true. This will cause the program to get stuck and stop responding.

Summary

Iteration is a fundamental concept in computer science that allows algorithms to perform repetitive tasks without redundant code. It alters the standard sequential flow of control, enabling programs to process large amounts of data, run simulations, and create interactive experiences. The two primary forms, fixed iteration (REPEAT n TIMES) and conditional iteration (REPEAT UNTIL), provide the flexibility to handle any repetitive task, whether the number of repetitions is known beforehand or depends on a dynamic condition. Mastering iteration is essential for building any non-trivial algorithm.