Misplaced Pages

Revision as of 16:26, 1 April 2006

This article is about the programming term. For the street on which Apple Computer's campus is located, see Infinite Loop (street).

An infinite loop is a sequence of instructions in a computer program which loops endlessly.

Looping

Looping is repeating a set of instructions until a specific condition is met. An infinite loop occurs when the condition will never be met, due to some inherent characteristic of the loop. There are a few situations when this is desired behavior. For example, many server programs such as Internet or database servers loop forever waiting for and servicing requests, though these may not be strictly considered infinite loops, because manual program termination still serves as a condition which exits the loop. Most often, the term is used for those situations when this is not the intended result; that is, when this is a bug. Such errors are most common among novice programmers, but can be made by experienced programs as well, and their causes can be quite subtle.

One common cause, for example, is that the programmer intends to iterate over a collection of items such as a linked list, executing the loop code once for each item. Improperly formed links can create a reference loop in the list, causing the code to continue forever because the program never reaches the end of the list.

Unexpected behavior in evaluating the terminating condition can also cause this problem. Here is an example (in C):

 float x = 0.1;
 while (x != 1.1) {
   x = x + 0.1;
   printf("x = %f\n", x);
 }

An example in Basic:

 10 x = x + 1
 20 Print x
 30 GoTo 10

On some systems, this loop will execute ten times as expected, but on some systems it will never terminate. The problem is that the loop terminating condition (x != 1.1) tests for exact equality of two floating point values, and the way floating point values are represented in many computers will make this test fail, because they cannot represent the value 1.1 exactly.

Because of the likelihood of tests for equality or not-equality failing unexpectedly, it is safer to use greater-than or less-than tests when dealing with floating-point values. For example, instead of testing whether x equals 1.1, one might test whether x <= 1.1, or x < 1.2, either of which would be certain to exit after a finite number of iterations. Another way to fix this particular example would be to use an integer as a loop index, counting the number of iterations that have been performed.

A similar problem occurs frequently in numerical analysis: in order to compute a certain result, an iteration is intended to be carried out until the error is smaller than a chosen tolerance. However, because of rounding errors during the iteration, the specified tolerance can never be reached, resulting in an infinite loop.

While most infinite loops can be found by close inspection of the code, there is no general method to determine whether a given program will ever halt or will run forever; this is the undecidability of the halting problem.

Pseudo-infinite loops

A pseudo-infinite loop is a loop that appears infinite but is really just a very long loop.

Impossible termination condition

An example in C:

unsigned int i;
for (i = 1; i > 0; i++)
  { loop code }

It appears that this will go on forever, but in fact the value of i will eventually reach the maximum value storable in an unsigned int and adding 1 to that number will wrap-around to 0, breaking the loop. The actual limit of i depends on the details of the system and compiler used. With arbitrary precision arithmetic, this loop would continue until the computer's memory could no longer contain i.

Infinite recursion

Infinite recursion, a special case of an infinite loop, is an infinite loop caused by recursion. The most trivial example of this is the term Ω in the lambda calculus, shown below in Scheme:

(define Ω
  (let ()
    (ω ω)))

Ω is an infinite recursion, and therefore has no normal form. When using structural recursion, infinite recursions are usually caused by a missing base case or by a faulty inductive step. An example of such a faulty structural recursion:

(define (sum-from-1-to n)
  (+ n (sum-from-1-to (sub1 n))))

The function sum-from-1-to will run out of stack space, as the recursion never stops — it is infinite. To correct the problem, a base case is added.

(define (sum-from-1-to' n)
  (cond
    ))

This revised function will only run out of stack space if n is less than 1 or n is too large; error checking would remove the first case. For information on recursive functions which never run out of stack space, see tail recursion.

See also

• Goto
• Recursion

• Programming bugs