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

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

Recursion on Numbers

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.

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.

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.

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.

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.

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.