Using recursion on the Arduino


#1

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.