next up previous
Contents Next: Abstraction Up: Programming Techniques Previous: Recursion on Numbers

Ensuring Proper Termination

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.

 

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 following notation illustrates why the above function does not terminate:
(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)))))))
        = ...
        = ...
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.
 

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.

 

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))))))

Yes, the above definition is correct and will terminate properly according to Rule of Thumb 7. We fulfill both requirements of the rule:
(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.



next up previous
Contents Next: Abstraction Up: Programming Techniques Previous: Recursion on Numbers



© Colin Allen & Maneesh Dhagat
November 1999