Controlling Infinite Evaluation
The general principle that
Mathematica 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,
Mathematica should go into an infinite loop. In fact,
Mathematica stops after a definite number of steps, determined by the value of the global variable
$RecursionLimit. You can always stop
Mathematica earlier by explicitly interrupting it.
This assignment could cause an infinite loop. Mathematica stops after a number of steps determined by $RecursionLimit.
Out[1]=  

When Mathematica stops without finishing evaluation, it returns a held result. You can continue the evaluation by explicitly calling ReleaseHold.
Out[2]=  

Global variables that limit infinite evaluation.
The variables
$RecursionLimit and
$IterationLimit control the two basic ways that an evaluation can become infinite in
Mathematica.
$RecursionLimit limits the maximum depth of the evaluation stack, or equivalently, the maximum nesting depth that would occur in the list structure produced by
Trace.
$IterationLimit limits the maximum length of any particular evaluation chain, or the maximum length of any single list in the structure produced by
Trace.
$RecursionLimit and
$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
Infinity. Note that on most computer systems, you should never set
$RecursionLimit=Infinity, as discussed in
"Memory Management".
Now infinite definitions like this are stopped after just 20 steps.
Out[5]=  

Without an end condition, this recursive definition leads to infinite computations. 
A fairly large structure is built up before the computation is stopped.
Out[7]=  

Here is another recursive definition. 
In this case, no complicated structure is built up, and the computation is stopped by $IterationLimit.
Out[9]=  

It is important to realize that infinite loops can take up not only time but also computer memory. Computations limited by
$IterationLimit do not normally build up large intermediate structures. But those limited by
$RecursionLimit often do. In many cases, the size of the structures produced is a linear function of the value of
$RecursionLimit. But in some cases, the size can grow exponentially, or worse, with
$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 righthand sides of your transformation rules will always be different from the lefthand sides. This ensures that evaluation will always "make progress", and
Mathematica 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".
Mathematica 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
Update[s] to tell
Mathematica to update all expressions involving
s.
Update[] tells
Mathematica to update absolutely all expressions.