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.

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

Ensuring Proper Termination

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

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

Ensuring Proper Termination

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

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

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

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