There are some functions which recur on a list of elements, but which return a number. The function ``length'' defined earlier is such a function. It takes an arbitrarily long list of elements and returns a count of its top-level elements. In the case of length, we are building a number by additions; at each level we add a one. One can also imagine a function which builds a number with consecutive multiplications. In both cases one must be careful in choosing which value to return at the terminating line.

RULE OF THUMB 5:When building a number value using +, return 0 at the

terminating line. When building a number value using

*, return 1 at the terminating line.

Using the ideas presented in previous sections, writing these functions should be simple. Again, we need to do three things: first we will check for the end of the list; second we will use the first element of the list in the addition (or multiplication); lastly the number will be added (or multipled) to the recursive call on the ``rest'' of the list. According to Rule of Thumb 5, we must remember that at the terminating line we must return 0 for addition and 1 for multiplication.

Example 5:Write a function, ``sum-of-list,'' which takes a list of numbers and returns

their sum. Write a similar function, ``product-of-list,'' which takes a

list of numbers and returns their product.

The following are the proposed solutions:

In the above examples, although we are building a number, we are still recurring on a list. It is also possible to recur on a number. The structure of recursion on numbers is very similar to that on simple lists.(defun sum-of-list (lst) (cond ((null lst) 0) (t (+ (first lst) (sum-of-list (rest lst)))))) (defun product-of-list (lst) (cond ((null lst) 1) (t (* (first lst) (product-of-list (rest lst))))))

RULE OF THUMB 6:When recurring on a number, do three things:

1. check for the termination condition;

2. use the number in some form;

3. recur with a changed form of the number.

The above problem is naturally recursive. In fact, it is very often represented mathematically as the following recurrence relation:

Example 6:The factorial of a non-negative integer, n, is

n * (n-1) * (n-2) * ... * 3 * 2 * 1.

Also, the factorial of 0 is 1. Implement the factorial function

in LISP.

This translates easily into the following LISP function definition:factorial(n) = {n * factorial(n-1) if n>0} {1 if n=0}

Let us try to identify the three element of Rule of Thumb 6:(defun factorial (n) (cond ((= n 0) 1) (t (* n (factorial (- n 1))))))

- (1)
- We check for termination by testing if n has been reduced to 0.
- (2)
- We use the number, n, in the multiplication.
- (3)
- We do recur on a changed form of the number, i.e. on n
decremented by one.

(factorial 4) = (* 4 (factorial 3)) = (* 4 (* 3 (factorial 2))) = (* 4 (* 3 (* 2 (factorial 1)))) = (* 4 (* 3 (* 2 (* 1 (factorial 0))))) = (* 4 (* 3 (* 2 (* 1 1)))) = (* 4 (* 3 (* 2 1))) = (* 4 (* 3 2)) = (* 4 6) = 24

Example 7:Write a function called ``remainder,'' which takes two positive non-zero

numbers, n and m, and returns the remainder when n is divided by m.

Our strategy will be to repeatedly subtract m from n till n is less than m; at this point n will be the value of the remainder. Let us proceed in the steps suggested by Rule of Thumb 6:

- (1)
- We know that we can stop when
**n < m**. This will be our termination condition and we will return the value of n. - (2)
- At each level of recursion we will subtract m from n; this represents our use of n.
- (3)
- We will recur with the value of n changed; specifically, we will
recur with n-m and m.

These steps translate into the following function definition:

The following notation gives an idea of the execution of ``remainder'':(defun remainder (n m) (cond ((< n m) n) (t (remainder (- n m) m))))

(remainder 30 7) = (remainder 23 7) = (remainder 16 7) = (remainder 9 7) = (remainder 2 7) = 2

November 1999