About me

About me


RSS feed

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

blog comments powered by Disqus