Recursion and Arduino aren’t words that you often find together in the same sentence. Most Arduino programming is iterative.
However, in my experience recursion often provides a simpler and more elegant way of solving many problems, and I was thinking about how recursion might help in typical Arduino programming problems, such as reading and writing I/O lines, serial input and output, and so on.
The classic example of a recursive function is factorial, but that doesn’t have any practical relevance to the Arduino. But here’s an example that does:
Counting ‘1’ bits
Let’s say you want to count the number of ‘1’ bits in a binary number. A practical application of this might be reading an input port connected to eight pushbuttons, and finding out how many buttons are pressed.
The traditional, iterative approach in Lisp would be:
(defun bts (b)
(let ((n 0))
(loop
(when (zerop b) (return n))
(setq n (+ n (logand b 1)))
(setq b (ash b -1)))))
Trying it out:
> (bts #b10110101)
5
Here’s a way of writing this recursively:
(defun bts (b)
(if (zerop b) 0
(+ (logand b 1) (bts (ash b -1)))))
The trick of expressing a problem as a recursive function is to express the solution in terms of applying the same function to a simpler version of the problem.
In this case the simpler version of the problem is the number of ‘1’ bits in the original bit pattern shifted right one position:
(bts (ash b -1))
The answer is then obtained by adding the bottom bit to this:
(+ (logand b 1) (bts (ash b -1)))
The last part of the recursive definition is to define a base case, to terminate the recursion. In this case it’s simply that zero has no ‘1’ bits:
(if (zerop b) 0 ...
In this example the recursive way of expressing the solution is simpler than the iterative approach, and we don’t need a variable, n, to count the bits.
Doubling up bits
Here’s a more interesting example:
Write a function to double up the bits in a number. So:
#b10010010
should become;
#b1100001100001100
In other words, each ‘1’ becomes ‘11’, and each ‘0’ becomes ‘00’. I’ve actually needed such a function in a program to plot double-sized bitmap characters on an Arduino display.
Here’s the recursive solution:
(defun bt2 (b)
(if (zerop b) 0
(+
(ash (bt2 (ash b -1)) 2)
(* 3 (logand b 1)))))
Let me know if you can think of any other examples using recursion that are appropriate to Arduino applications.