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

© Colin Allen & Maneesh Dhagat
March 2007