## A case for recursion

23rd May 2016

I wish articles about recursive programming would stop using the factorial function as the example:

`(defun fact (n) (if (zerop n) 1 (* n (fact (1- n)))))`

It's so easy to program it using iteration, and it's clear that the iterative version is better, so the example just supports the notion that I've actually seen expressed that "recursion is a curiosity only used in computer science teaching, but not useful in real world programming".

For some time I've been looking for a simple example that makes a compelling case that recursive programming is often simpler, more intuitive, and less error-prone than iteration. Here's a suggestion:

### A candidate for recursion

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.

Alternatively, here's the recursive approach. First we find the sum of all the temperatures:

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

This is far simpler, and less error-prone, than the iterative approach. 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))))))```

Finally, here's the average, ave:

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

### Combining sum and tot

As a final step we could combine sum and tot into a single function:

```(defun ave (l)
(cond
((null l) (list 0 0))
((numberp l) (list l 1))
(t (map 'list #'+ (ave (first l)) (ave (rest l))))))```

Then we can calculate the average with:

```(apply #'/ (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)))))```

### Multiple values

I also tried combining sum and tot by returning multiple values, but it's a bit tricky. The function multiple-value-call looks like it might be useful, but it isn't really.