Repetition and Iteration

Do It Again—But with a Rule

Suppose we want to add the integers from \(1\) through \(5\).

We could write

Or we could describe a repeated process:

1. Start with total \(=0\).
2. Add the next integer to total.
3. Move to the following integer.
4. Repeat until \(5\) has been added.

The repeated action is not random. It follows a precise update rule.

What Is Repetition?

Repetition means performing an action more than once.

In mathematics, repeated action appears in familiar forms:

• repeated addition,
• repeated multiplication,
• successive approximation,
• generating sequence terms,
• checking each item in a list.

For example,

is repeated addition and can be compressed into

Algorithms often make the repetition itself explicit because the number of repetitions or stopping condition may vary.

What Is Iteration?

Iteration is structured repetition in which an operation or group of operations is performed repeatedly, usually while some state changes.

A typical iteration has:

Fixed-Count Repetition

Sometimes the number of repetitions is known in advance.

Example

Add \(3\) to a total exactly five times.

total = 0

REPEAT 5 TIMES
    total = total + 3
END REPEAT

The successive totals are

The process performs exactly five updates.

Condition-Controlled Repetition

Sometimes we do not know in advance exactly how many repetitions will be needed.

Instead, repetition continues while a condition remains true.

Example

WHILE x >= 10
    x = x / 10
END WHILE

If

the values are approximately

The loop stops when

The Structure of a Loop

Loop State

The state of an iteration is the collection of current values that matter to the next step.

For example, while summing

we might track:

• the current integer \(i\),
• the running total \(S\).

At one moment the state might be

After adding \(4\), the state becomes

Iteration can therefore be viewed as repeated transformation of state.

Counters

A counter tracks how many repetitions have occurred or which position is currently being processed.

Example

i = 1

WHILE i <= 5
    output i
    i = i + 1
END WHILE

The counter values are

The update

moves the loop toward termination.

Accumulators

An accumulator stores a result that is built gradually across iterations.

Sum Accumulator

total = 0

FOR each value x
    total = total + x
END FOR

The update rule is

Product Accumulator

To multiply a sequence of values, begin with

and repeatedly update

The initial value matters: sums naturally begin at \(0\), while products naturally begin at \(1\).

Update Rules

The update rule determines how one iteration leads to the next.

Examples include:

The arrow notation

means “replace the current value of \(x\) with the old value plus \(1\).”

It is an assignment or state update, not an ordinary algebraic equation.

Stopping and Termination

A condition-controlled loop must have some way to stop.

Consider:

WHILE n > 0
    n = n - 1
END WHILE

For a nonnegative integer input, \(n\) decreases by \(1\) each repetition and eventually reaches \(0\).

But this loop does not progress:

WHILE n > 0
    output n
END WHILE

If \(n>0\) initially, the state never changes, so the condition remains true forever.

Loop Invariants

A loop invariant is a statement that remains true before and after every iteration.

Invariants help explain why an algorithm is correct.

Example: Running Sum

Suppose after processing the first \(k\) values, the variable \(S\) equals their sum.

That statement is an invariant:

When the next value \(x_{k+1}\) is added,

the invariant becomes

At termination, the invariant tells us that \(S\) contains the full sum.

Nested Iteration

A loop may contain another loop.

Example: Grid Positions

FOR row = 1 TO 3
    FOR column = 1 TO 4
        process (row, column)
    END FOR
END FOR

The inner loop runs \(4\) times for each of \(3\) outer-loop repetitions.

Total processed positions:

Nested iteration often produces multiplicative growth in the amount of work.

Iteration and Sequences

An iterative update naturally generates a sequence of states.

Start with

and repeatedly apply

The states are

The recurrence describes the update rule, while iteration describes the process of repeatedly applying it.

Iteration and Recursion

Iteration and recursion can often describe the same repeated structure in different ways.

For example, factorial can be defined recursively by

with

An iterative version is:

product = 1

FOR i = 1 TO n
    product = product * i
END FOR

Both compute the same mathematical object, but they organize the repeated work differently.

Efficiency and Repeated Work

Loops make repeated work visible, which makes efficiency easier to analyze.

A loop that processes every item in a list of \(n\) values performs work that grows roughly with \(n\).

A nested loop that compares every item with every other item may perform work that grows roughly with

This does not make nested loops automatically bad. It tells us how the amount of work scales as the input grows.

Later computational analysis will make these ideas more precise.

Practical Applications

Mathematics

Iteration generates sequences, approximates roots, sums series, and performs repeated algebraic operations.

Data Processing

Loops process records, rows, measurements, or elements of a collection.

Simulation

A model repeatedly updates its state from one time step to the next.

Finance

Compound growth can be modeled by repeatedly updating an account balance.

Engineering

Iterative numerical methods refine estimates until an error or tolerance condition is satisfied.

Worked Examples

Example 1: Count from 1 to 5

i = 1

WHILE i <= 5
    output i
    i = i + 1
END WHILE

Output:

Example 2: Sum the First Five Positive Integers

total = 0

FOR i = 1 TO 5
    total = total + i
END FOR

The totals evolve as

Final output:

Example 3: Product of the First Four Positive Integers

product = 1

FOR i = 1 TO 4
    product = product * i
END FOR

Example 4: Repeated Halving

Start with

While

replace \(x\) with \(x/2\).

The states are

The loop stops at

Example 5: Generate a Geometric Sequence

Start with

Repeatedly update

The values are

Each iteration produces the next term.

Example 6: Nested Counting

If an outer loop runs \(5\) times and an inner loop runs \(3\) times during each outer repetition, then the inner operation occurs

times.

Common Errors

1. Forgetting to Update the Loop State

If the variables in the condition never change, the loop may never terminate.

2. Starting the Counter at the Wrong Value

Beginning at \(0\) instead of \(1\), or vice versa, can shift every repetition.

3. Stopping One Iteration Too Early or Too Late

Boundary conditions such as

and

produce different numbers of iterations.

4. Using the Wrong Accumulator Identity

A sum accumulator usually starts at \(0\); a product accumulator usually starts at \(1\).

5. Confusing Assignment with Equality

\[ x\leftarrow x+1 \]

means update \(x\). It is not the algebraic equation \(x=x+1\).

6. Assuming Repetition Guarantees Progress

A loop must change state in a way that can eventually satisfy its stopping condition.

Practice

Fixed Count

How many times does the body execute?

FOR i = 1 TO 7
    output i
END FOR

Accumulator

What should a variable usually start at if it will accumulate a product?

Termination

Does this loop terminate for positive integer \(n\)?

WHILE n > 0
    n = n - 2
END WHILE

Sequence

Start with \(a_0=2\) and repeatedly apply

What are the first four terms starting with \(a_0\)?

Nested Iteration

An outer loop runs \(4\) times. An inner loop runs \(6\) times for each outer iteration. How many total inner-loop executions occur?

The Deeper Idea

Iteration turns a single transformation into a chain of transformations.

where each state is produced from the previous one by an update rule.

This connects iteration to several mathematical structures:

• sequences list successive states,
• recurrence relations define how one state produces the next,
• functions can serve as update rules,
• logic controls whether another update occurs,
• invariants describe what remains true throughout the process.

So iteration is not merely “doing something many times.”

It is repeated state transformation under a rule.

Summary

• Repetition means performing an action more than once.
• Iteration is structured repetition in which state changes according to an update rule.
• Fixed-count loops repeat a known number of times.
• Condition-controlled loops continue while or until a condition is satisfied.
• Loop state is the collection of current values needed by the process.
• Counters track positions or repetition counts.
• Accumulators build sums, products, or other results across iterations.
• Update rules transform the current state into the next state.
• Termination requires a path toward a state where repetition stops.
• Loop invariants describe properties preserved throughout iteration.
• Nested loops place one repeated process inside another.
• Iterative rules naturally generate sequences.
• Iteration and recursion can represent the same repeated mathematical structure in different ways.
• The number and arrangement of repetitions affect computational efficiency.

Iteration gives repetition mathematical structure. Once we identify the initial state, condition, body, and update rule, repeated work becomes something we can trace, prove correct, analyze for termination, and improve for efficiency.

Algorithms and Computational Thinking

• Previous: Decision Rules and Branching
• Algorithms and Computational Thinking — return to the lesson directory.