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.