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.
blog comments powered by Disqus