Controlling Infinite Evaluation

The general principle that the Wolfram Language follows in evaluating expressions is to go on applying transformation rules until the expressions no longer change. This means, for example, that if you make an assignment like x=x+1, the Wolfram Language should go into an infinite loop. In fact, the Wolfram Language stops after a definite number of steps, determined by the value of the global variable (RefLink[$RecursionLimit, paclet:ref/$RecursionLimit]). You can always stop the Wolfram Language earlier by explicitly interrupting it.

This assignment could cause an infinite loop. The Wolfram Language stops after a number of steps determined by (RefLink[$RecursionLimit, paclet:ref/$RecursionLimit]):

x=x+1

When the Wolfram Language stops without finishing evaluation, it returns a held result. You can continue the evaluation by explicitly calling (RefLink[ReleaseHold, paclet:ref/ReleaseHold]):

ReleaseHold[%]

Global variables that limit infinite evaluation.

Here is a circular definition, whose evaluation is stopped by (RefLink[$IterationLimit, paclet:ref/$IterationLimit]):

{a,b}={b,a}

The variables (RefLink[$RecursionLimit, paclet:ref/$RecursionLimit]) and (RefLink[$IterationLimit, paclet:ref/$IterationLimit]) control the two basic ways that an evaluation can become infinite in the Wolfram Language. (RefLink[$RecursionLimit, paclet:ref/$RecursionLimit]) limits the maximum depth of the evaluation stack, or equivalently, the maximum nesting depth that would occur in the list structure produced by (RefLink[Trace, paclet:ref/Trace]). (RefLink[$IterationLimit, paclet:ref/$IterationLimit]) limits the maximum length of any particular evaluation chain, or the maximum length of any single list in the structure produced by (RefLink[Trace, paclet:ref/Trace]).

(RefLink[$RecursionLimit, paclet:ref/$RecursionLimit]) and (RefLink[$IterationLimit, paclet:ref/$IterationLimit]) are by default set to values that are appropriate for most computations, and most computer systems. You can, however, reset these variables to any integer (above a lower limit), or to (RefLink[Infinity, paclet:ref/Infinity]). Note that on most computer systems, you should never set (RefLink[$RecursionLimit, paclet:ref/$RecursionLimit])=(RefLink[Infinity, paclet:ref/Infinity]), as discussed in "Memory Management".

This resets (RefLink[$RecursionLimit, paclet:ref/$RecursionLimit]) and (RefLink[$IterationLimit, paclet:ref/$IterationLimit]) to 20:

$RecursionLimit=$IterationLimit=20

Now infinite definitions like this are stopped after just 20 steps:

t={t}

Without an end condition, this recursive definition leads to infinite computations:

fn[n_]:={fn[n-1],n}

A fairly large structure is built up before the computation is stopped:

fn[10]

Here is another recursive definition:

fm[n_]:=fm[n-1]

In this case, no complicated structure is built up, and the computation is stopped by (RefLink[$IterationLimit, paclet:ref/$IterationLimit]):

fm[0]

It is important to realize that infinite loops can take up not only time but also computer memory. Computations limited by (RefLink[$IterationLimit, paclet:ref/$IterationLimit]) do not normally build up large intermediate structures. But those limited by (RefLink[$RecursionLimit, paclet:ref/$RecursionLimit]) often do. In many cases, the size of the structures produced is a linear function of the value of (RefLink[$RecursionLimit, paclet:ref/$RecursionLimit]). But in some cases, the size can grow exponentially, or worse, with (RefLink[$RecursionLimit, paclet:ref/$RecursionLimit]).

An assignment like x=x+1 is obviously circular. When you set up more complicated recursive definitions, however, it can be much more difficult to be sure that the recursion terminates, and that you will not end up in an infinite loop. The main thing to check is that the right-hand sides of your transformation rules will always be different from the left-hand sides. This ensures that evaluation will always "make progress", and the Wolfram Language will not simply end up applying the same transformation rule to the same expression over and over again.

Some of the trickiest cases occur when you have rules that depend on complicated /; conditions (see "Putting Constraints on Patterns"). One particularly awkward case is when the condition involves a "global variable". The Wolfram Language may think that the evaluation is finished because the expression did not change. However, a side effect of some other operation could change the value of the global variable, and so should lead to a new result in the evaluation. The best way to avoid this kind of difficulty is not to use global variables in /; conditions. If all else fails, you can type (RefLink[Update, paclet:ref/Update])[s] to tell the Wolfram Language to update all expressions involving s. (RefLink[Update, paclet:ref/Update])[] tells the Wolfram Language to update absolutely all expressions.