Using recursion on the Arduino


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))
     (when (zerop b) (return n))
     (setq n (+ n (logand b 1)))
     (setq b (ash b -1)))))

Trying it out:

> (bts #b10110101)

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:


should become;


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.