loop invariant

A loop invariant is a statement that stays true every time a loop comes back around — before the first pass, after each pass, and when the loop finally stops. It is the steady fact you can lean on amid all the changing variables. A homely analogy: as you climb a staircase one step at a time, the invariant is 'every stair below me has already been climbed.' The step you are on changes constantly, but that sentence is true at the bottom, true after each step, and true at the top — and at the top it tells you something useful: the whole staircase is climbed.

Programmers use invariants to reason about why a loop is correct, not just whether it happens to produce the right answer on a few test cases. The argument has three parts, like proof by induction. Initialization: the invariant is true before the loop starts. Maintenance: if it is true at the start of an iteration, the loop body keeps it true at the end. Termination: when the loop exits, the invariant — combined with the reason the loop stopped — gives you the result you wanted. Finding the right invariant is often the moment a tricky loop suddenly makes sense.

Take a loop that finds the maximum of an array by scanning left to right. A good invariant is: 'max holds the largest value among the elements seen so far (a[0..i-1]).' It is true before we look at anything (vacuously, with max set to the first element), each step preserves it by comparing the new element, and when the scan ends — having seen every element — the invariant says max is the largest of them all. The invariant turns 'I think this works' into 'I can see why this works,' which is the whole reason it earns a name.