uLisp

Recursion

Many difficult programming problems are easier to solve if you express the solution in terms of a simpler version of the same problem. As an example consider the famous fibonacci sequence:

1 1 2 3 5 8 13 21 34

where the first two terms are 1, and each subsequent term is the sum of the two previous terms.

We could define the method of finding the nth term as:

• Find the (n-1)th term.
• Find the (n-2)th term.
• Add them together.

This is called a recursive definition because it defines the answer in terms of the function we're trying to solve, and Lisp is an ideal language for expressing problems recursively

To ensure that the process stops at some point we need to specify that the first two terms are 1:

• If n=1 or n=2 the result is 1.

Here's the definition, which is almost a direct translation of the above description:

(defun fib (n)
  (if (< n 3) 1
    (+ (fib (- n 1)) (fib (- n 2)))))

You can verify that:

(fib 10)

gives 55.

Recursion with lists

Here's another example showing how a recursive approach can make working with list structures much easier and more intuitive.

Suppose we have a data logging application that measures the weekend temperature every 6 hours, and stores the results as a list of values:

(7 11 21 12)

Every week we accumulate a list of two such lists, so after a week the data looks similar to this:

((7 11 21 12) (6 9 20 11))

Then each week's measurements are put into a list, one per week. For example, here's three weeks' data:

(((7 11 21 12) (6 9 20 11)) ((7 8 19 10) (6 10 18 9)) ((6 9 19 10) (7 8 19 10)))

Suppose we want to find the mean temperature over all the data. One way would involve iterating over the weeks, days, and 6-hour periods using three nested loops.

Here's the recursive approach. First we find the sum of all the temperatures; we simply say:

• The sum is the sum of the first item, plus the sum of the rest of the items.
• If the item is a number, the sum is just that number.
• If an item is an empty list, nil, the sum is zero.

This is far simpler, and less error-prone, than the iterative approach. Here's the definition of sum in uLisp:

(defun sum (l)
  (cond
   ((null l) 0)
   ((numberp l) l)
   (t (+ (sum (first l)) (sum (rest l))))))

Because there are three options it's easier to use a cond statement, although you could use two nested if statements instead.

We also need the total number of measurements. The solution, tot, is very similar:

(defun tot (l)
  (cond
   ((null l) 0)
   ((numberp l) 1)
   (t (+ (tot (first l)) (tot (rest l))))))

In fact you could combine sum and tot into a single function using a second parameter.

Finally, here's the average, ave:

(defun ave (l)
  (/ (sum l) (tot l)))

We can try it as follows:

> (ave '(((7 11 21 12) (6 9 20 11)) ((7 8 19 10) (6 10 18 9)) ((6 9 19 10) (7 8 19 10))))
11