next up previous
Contents Next: Ensuring Proper Termination Up: Programming Techniques Previous: Recursion on Nested

Recursion on Numbers

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.

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.

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.

The following are the proposed solutions:

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

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.

 

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.

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

      factorial(n) = {n * factorial(n-1) if n> 0}
                     {1                  if n=0}
This translates easily into the following Lisp function definition:
          (defun factorial (n)
             (cond ((= n 0) 1)
                   (t (* n (factorial (- n 1))))))
Let us try to identify the three element of Rule of Thumb 6:
(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.

The following notation gives an idea of the execution of ``factorial'':
(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:

          (defun remainder (n m)
             (cond ((< n m) n)
                   (t (remainder (- n m) m))))
The following notation gives an idea of the execution of ``remainder'':
(remainder 30 7)
        = (remainder 23 7)
        = (remainder 16 7)
        = (remainder 9 7)
        = (remainder 2 7)
        = 2


next up previous
Contents Next: Ensuring Proper Termination Up: Programming Techniques Previous: Recursion on Nested



© Colin Allen & Maneesh Dhagat
March 2007