Often it happens that the Lisp programmer unknowingly implements an infinite loop. This could happen in two different ways: an infinite ``do'' loop, or an improper recursion. In the first case, it may be that the programmer is using the general ``do'' construct and has specified a test for termination that will never occur. This problem can be avoided by using the more specific constructs ``dotimes'' or ``dolist'' (chapter 3). These constructs have a built-in test for termination; ``dotimes'' iterates a specified number of times, and ``dolist'' iterates once for each element in a given list. Improper recursion, however, is often more difficult to discover.

The following notation illustrates why the above function does not terminate:

Example 8:The following definition wrongly implements the function to determine

the length of a list:

(defun length (lst)

(cond ((null lst) 0)

(t (+ 1 (length lst)))))

The list is passed-in unmodified in the recursive call. Such simple mistakes are very common, and their frequency increases with longer and more complicated programs. Compare this definition of ``length'' with the one given in section 4.2.(length '(a b c)) = (+ 1 (length '(a b c))) = (+ 1 (+ 1 (length '(a b c)))) = (+ 1 (+ 1 (+ 1 (length '(a b c))))) = (+ 1 (+ 1 (+ 1 (+ 1 (length '(a b c)))))) = (+ 1 (+ 1 (+ 1 (+ 1 (+ 1 (length '(a b c))))))) = ... = ...

RULE OF THUMB 7:To ensure proper termination do two things:

(1) make sure that you are changing at least one argument

in your recursive call;

(2) make sure that your test for termination looks at the

arguments that change in the recursive call.

Yes, the above definition is correct and will terminate properly according to Rule of Thumb 7. We fulfill both requirements of the rule:

Example 9:A function, ``exp,'' takes two positive, non-zero integers, x and y, and

raises x to the y power. Will the following recursive definition for

``exp'' terminate properly?

(defun exp (x y)

(cond ((= y 0) 1)

(t (* x (exp x (- y 1))))))

- (1)
- We are changing at least one argument in the recursive call, namely y, which is decremented by one.
- (2)
- In our test for termination,
`(= y 0)`

, we are using an argument that we change in the recursive call, namely y.

RULE OF THUMB 8:

Two simple cases may occur when changing an argument in a

recursive call:

(1) if you are using ``rest'' to change an argument which is

a list, use ``null'' in the test for termination;

(2) if you are decreasing an argument which is a number,

compare it with 0 in the test for termination.

March 2007