Why This Matters
Iteration makes state explicit. A loop variable, accumulator, and invariant often give a simpler implementation than recursive calls, especially for long linear scans.
Core Idea
A loop should have a loop invariant: a statement that remains true before and after each iteration.
Worked example: when summing an array, the invariant after processing index i is that the accumulator equals the sum of all elements before i.
| Pattern | Typical use |
|---|---|
| counted loop | arrays and ranges |
| while loop | unknown stopping time |
| two-pointer loop | sorted arrays or windows |
| accumulator loop | sums, counts, products |
Common Mistakes
- Off-by-one boundaries.
- Mutating loop state in multiple places.
- Using recursion when an iterative loop avoids stack depth risk.
Exercises
- State the loop invariant for finding the maximum of an array.
- Convert recursive factorial to a loop.
- Identify the off-by-one error in a loop from
0throughn.
Next Topics
- Fibonacci: recursive, iterative, matrix, and golden-ratio forms
- Two pointers
- Dynamic programming
- Complexity analysis
References
- Bentley. Programming Pearls (2nd ed., 2000). Ch. 4.
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 2.