Loop termination conditions

Question

These for-loops are among the first basic examples of formal correctness proofs of algorithms. They have different but equivalent termination conditions:

1   for ( int i = 0; i != N; ++i )

2   for ( int i = 0; i < N; ++i )

The difference becomes clear in the postconditions:

• The first one gives the strong guarantee that i == N after the loop terminates.

• The second one only gives the weak guarantee that i >= N after the loop terminates, but you will be tempted to assume that i == N.

If for any reason the increment ++i is ever changed to something like i += 2, or if i gets modified inside the loop, or if N is negative, the program can fail:

• The first one may get stuck in an infinite loop. It fails early, in the loop that has the error. Debugging is easy.

• The second loop will terminate, and at some later time the program may fail because of your incorrect assumption of i == N. It can fail far away from the loop that caused the bug, making it hard to trace back. Or it can silently continue doing something unexpected, which is even worse.

Which termination condition do you prefer, and why? Are there other considerations? Why do many programmers who know this, refuse to apply it?

Answer 1

I tend to use the second form, simply because then I can be more sure that the loop will terminate. I.e. it's harder to introduce a non-termination bug by altering i inside the loop.

Of course, it also has the slightly lazy advantage of being one less character to type ;)

I would also argue, that in a language with sensible scope rules, as i is declared inside the loop construct, it shouldn't be available outside the loop. This would mitigate any reliance on i being equal to N at the end of the loop...

Answer 2

We shouldn't look at the counter in isolation - if for any reason someone changed the way the counter is incremented they would change the termination conditions and the resulting logic if it's required for i==N.

I would prefer the the second condition since it's more standard and will not result in endless loop.

Answer 3

In C++, using the != test is preferred for generality. Iterators in C++ have various concepts, like input iterator, forward iterator, bidirectional iterator, random access iterator, each of which extends the previous one with new capabilities. For < to work, random access iterator is required, whereas != merely requires input iterator.

Answer 4

If you trust your code, you can do either.

If you want your code to be readable and easily understood (and thus more tolerant to change from someone who you've got to assume to be a klutz), I'd use something like;

for ( int i = 0 ; i >= 0 && i < N ; ++i)