   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

(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.

NOTE: The example above again illustrates that you are allowed to redefine functions that are built into Lisp. Programmer beware!!
``` 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.

```   Contents Next: Abstraction Up: Programming Techniques Previous: Recursion on Numbers

© Colin Allen & Maneesh Dhagat
March 2007