Repetition.
We have learned about sequence — instructions executing one after another. We have learned about branching — programs choosing between different paths.
Today, we learn about repetition. The same instructions executing multiple times.
Repetition is fundamental. Without it, programs would be limited to doing things once. With repetition, programs can do things as many times as needed.
Imagine you need to add ten numbers together. Without repetition, you would write ten separate addition instructions.
Now imagine you need to add a thousand numbers. Would you write a thousand instructions? That is impractical.
Now imagine you do not know how many numbers you will receive. The count depends on user input. How would you write instructions for an unknown number of items?
You cannot. Not without repetition.
Repetition allows a small number of instructions to execute many times. Instead of writing a thousand instructions, you write a few instructions and repeat them a thousand times.
This is the power of repetition. It scales. A program that handles ten items can handle ten thousand items with the same instructions.
What does repetition look like?
We have a block of instructions. When the program reaches this block, it executes the instructions. Then, instead of moving forward, it goes back to the beginning of the block and executes them again.
And again. And again.
Each time through the block is called an iteration. First iteration, second iteration, third iteration, and so on.
The instructions are the same each time. But the state is different. Because each iteration changes the state, the next iteration starts with a different state than the previous one.
This is crucial. The instructions repeat, but the state evolves. Each iteration builds on the results of the previous iteration.
Let us trace a simple repetition.
We want to compute the sum of numbers from one to five.
We have a variable called total, starting at zero. We have a variable called counter, starting at one.
Each iteration: add counter to total. Then increase counter by one.
First iteration: total is zero plus one, which is one. Counter becomes two.
Second iteration: total is one plus two, which is three. Counter becomes three.
Third iteration: total is three plus three, which is six. Counter becomes four.
Fourth iteration: total is six plus four, which is ten. Counter becomes five.
Fifth iteration: total is ten plus five, which is fifteen. Counter becomes six.
After five iterations, total is fifteen. That is the sum of one through five.
Notice: the instructions were the same each time. Add counter to total. Increase counter. But the state changed. Each iteration saw different values for total and counter. Each iteration produced a different result.
There is a critical question: when does repetition stop?
If the instructions repeat forever, the program never finishes. It runs indefinitely. This is usually a mistake. We call it an infinite loop.
For repetition to be useful, it must eventually stop. There must be a point where the program says: "Enough. Stop repeating. Move on."
This is the termination condition. It is a condition, like the conditions we use for branching. When the condition becomes true, the repetition stops.
In our example, the termination condition might be: stop when counter is greater than five.
First iteration: counter is one. One is not greater than five. Continue.
Second iteration: counter is two. Two is not greater than five. Continue.
And so on, until...
Sixth check: counter is six. Six is greater than five. Stop.
The termination condition determines how many iterations occur. Change the condition, and you change how many times the instructions repeat.
Every repetition has three parts.
One: the initial state. Before repetition begins, there is some state. This is the starting point.
Two: the body. This is the block of instructions that repeats. Each iteration executes these instructions.
Three: the termination condition. This is the check that determines whether to continue or stop. It is evaluated before or after each iteration.
These three parts define the repetition completely.
The initial state sets up the starting values. The body does the work, modifying the state each iteration. The termination condition ensures the repetition eventually stops.
If any part is missing or wrong, the repetition fails. Missing initial state means starting from undefined values. Missing body means nothing happens. Missing or wrong termination condition means infinite loop.
Let us think more about termination conditions.
A termination condition is a question about state. Just like the conditions in branching, it evaluates to true or false.
When the condition is false, the repetition continues. When the condition becomes true, the repetition stops.
For the repetition to eventually stop, something must change to make the condition true. Usually, the body modifies some value that the condition checks.
In our example, the body increases counter. The condition checks if counter is greater than five. Eventually, counter becomes six, the condition becomes true, and the repetition stops.
If the body did not modify counter, the condition would never become true. Counter would stay at one forever. The repetition would never stop. Infinite loop.
This is a common bug: forgetting to modify the value that the termination condition checks. The condition never becomes true. The program runs forever.
Always verify: does the body move the state toward the termination condition?
Many repetitions are controlled by counting.
We want to repeat something a specific number of times. We use a counter. Each iteration, we increase the counter. When the counter reaches the target, we stop.
This is the most common pattern.
Start counter at zero. Repeat while counter is less than target. Each iteration, do the work and increase counter by one.
If target is five, we get five iterations. Counter goes from zero to one to two to three to four. When counter becomes five, the condition "counter less than target" becomes false. We stop.
Counting is simple and reliable. You know exactly how many iterations will occur. The termination condition is easy to verify. The progress toward termination is clear.
But not all repetitions are based on counting. Some continue until a specific state is reached. Some continue until external input arrives. The principle is the same: there must be a condition, and the state must evolve toward satisfying that condition.
Repetition is often used to accumulate results.
We start with some initial value. Each iteration adds to that value. After many iterations, we have accumulated a final result.
Our sum example is accumulation. We start with total equal to zero. Each iteration adds a number to total. After all iterations, total contains the sum.
Accumulation is powerful because it builds up results gradually. No single instruction computes the final answer. The answer emerges from many small contributions.
This pattern appears everywhere. Computing averages: accumulate sum, count items, divide at the end. Finding maximum: compare each item to current maximum, update if larger. Building strings: start empty, add characters one by one.
All these use repetition with accumulation. Each iteration contributes a little. The final result is the combination of all contributions.
Remember invariants? Conditions that must always hold?
Invariants are especially important in repetition.
With repetition, you execute instructions many times. Each iteration changes state. If any iteration violates an invariant, you have a bug. And with many iterations, there are many chances for bugs.
A well-designed repetition maintains its invariants across all iterations. Each iteration starts with the invariant true. Each iteration ends with the invariant still true.
For example, in our sum program, we might have an invariant: total equals the sum of all numbers from one to counter minus one.
Before the first iteration: total is zero, counter is one. Sum of numbers from one to zero is zero. Invariant holds.
After each iteration: we add counter to total, then increase counter. The invariant still holds.
This invariant helps us verify correctness. If it holds after every iteration, and it holds when we stop, then total has the correct sum.
Thinking about invariants during repetition helps you write correct code. What must be true at the start of each iteration? What must be true at the end? Does each iteration preserve these conditions?
Let us summarize.
Repetition allows the same instructions to execute multiple times. Each execution is an iteration.
Each iteration changes state. The instructions are the same, but the state evolves.
Repetition must eventually stop. The termination condition determines when to stop.
The termination condition checks state. The body must modify state to eventually satisfy the condition. Otherwise, infinite loop.
Many repetitions count iterations. Others repeat until a specific state is reached.
Repetition often accumulates results. Each iteration contributes to a final answer.
Invariants help verify correctness. Each iteration should maintain the invariants.
Repetition is fundamental. It allows programs to handle any amount of work with a fixed amount of code.