Welcome to the World of Iteration!

Have you ever had to do a repetitive task, like writing lines on a chalkboard or doing 50 jumping jacks? In programming, we don't like to do the same thing over and over again manually. That’s where Iteration comes in! Iteration is a fancy word for "looping" or repeating a set of instructions. It is one of the three fundamental building blocks of all algorithms (along with sequencing and selection).

By the end of these notes, you’ll understand how to make your programs work harder, so you don’t have to!

1. What is Iteration?

Iteration is the repetitive execution of a block of statements in an algorithm. Instead of writing the same code ten times, we write it once and tell the computer how many times to repeat it or under what conditions it should keep going.

Analogy: Think of a song. Instead of the songwriter writing the chorus out four separate times, they just write it once and indicate that it should be played after every verse. That is iteration in music!

2. The Two Main Types of Loops

In the AP CSP Exam Reference Sheet, there are two primary ways to show iteration. Let's break them down.

A. REPEAT n TIMES

This is used when you know exactly how many times you want a block of code to run before you even start.

The Syntax:
REPEAT \(n\) TIMES
{
    <block of statements>
}

How it works: The computer sees the number \(n\) and performs the actions inside the curly braces exactly that many times. If \(n\) is 5, the loop runs 5 times and then stops.

B. REPEAT UNTIL (condition)

This is a conditional loop. You use this when you don't know exactly how many times the loop will run, but you know when you want it to stop.

The Syntax:
REPEAT UNTIL (condition)
{
    <block of statements>
}

How it works: The computer checks the condition before it runs the code inside. If the condition is false, the code inside runs. It keeps repeating until the condition becomes true.

Important Tip: If the condition is already true the very first time the computer checks it, the code inside the loop will never run!

Quick Review:
- REPEAT n TIMES: Use when the count is fixed.
- REPEAT UNTIL: Use when you are waiting for a specific goal or state.

3. Determining Results and Side Effects

When you see a loop on the AP Exam, you often have to figure out what the variables will be at the end. This is called "hand tracing."

Example Trace:
\(x \leftarrow 1\)
REPEAT 3 TIMES
{
    \(x \leftarrow x + 2\)
}
DISPLAY(\(x\))

Step-by-step logic:
1. Start: \(x = 1\)
2. Iteration 1: \(x\) becomes \(1 + 2 = 3\)
3. Iteration 2: \(x\) becomes \(3 + 2 = 5\)
4. Iteration 3: \(x\) becomes \(5 + 2 = 7\)
5. The loop finishes. The final value displayed is \(7\).

4. The "Infinite Loop" Trap

An infinite loop occurs when the ending condition of a REPEAT UNTIL loop never becomes true. This causes the program to run forever (or until the computer crashes!).

Example of an Infinite Loop:
\(x \leftarrow 10\)
REPEAT UNTIL (\(x = 0\))
{
    \(x \leftarrow x + 1\)
}

Why is this infinite? Since \(x\) starts at 10 and we keep adding 1, it will keep getting bigger (\(11, 12, 13...\)). It will never reach 0, so the loop will never stop!

Did you know? Most modern computers have ways to force-quit a program if it gets stuck in an infinite loop, but in the early days of computing, this could completely lock up a machine!

5. Common Mistakes to Avoid

Don't worry if this seems tricky at first; even professional programmers make these mistakes!

  • Off-by-One Errors: This happens when a loop runs one time too many or one time too few. Always check if your loop should run \(n\) or \(n-1\) times.
  • Forgetting to Update: In a REPEAT UNTIL loop, if you don't change the variable inside the loop (like adding to \(x\)), the condition will never change, and you'll get an infinite loop.
  • Starting Condition: Remember that if the condition is true at the start, REPEAT UNTIL skips the code entirely.

6. Expressing Iteration in Different Ways

Algorithms can be written in many formats, not just code. You might see iteration expressed as:

  • Natural Language: "Keep walking until you reach the wall."
  • Flowcharts: A diamond shape (decision) with an arrow pointing back up to a previous step.
  • Pseudocode: The REPEAT blocks we've been using!

Note: Iteration is also used heavily with Lists (Big Idea 3.10) to look at every item in a collection. You'll see a special version called FOR EACH when you study that chapter!

Key Takeaways Summary

1. Iteration is repeating a process to simplify code and handle multiple data points.
2. REPEAT n TIMES is for a specific, known number of repetitions.
3. REPEAT UNTIL continues as long as the condition is false and stops the moment it becomes true.
4. Infinite Loops happen when the stop condition is never met.
5. Hand Tracing is the best way to determine the result of a loop—just keep a small table of variable changes for each "lap" the loop takes.