« Older: C Pointers « Older
Newer: Comparing Floats »Newer »

# Recursion

I really like recursion and I find that it is an option that we often fail to consider when writing code. There have been times that I have thought of needlessly complicated solutions to a problem because, in general, I don’t look for recursive solutions early. I was reminded about this recently when looking at a StackOverflow question on calculating:

$$ log(\frac{z + 1}{z - 1}) $$

using continued fractions, implementing code to calculate it using the following formula:

$$ log(\frac{z + 1}{z - 1}) = \frac{2 \cdot z}{1 - \frac{z^2}{3 - \frac{4 \cdot z^2}{(2 \cdot n - 1) - \frac {n^2 \cdot z^2}{...}}}} $$

where $n$ is the count of divisions, i.e. in the line under the first division $n = 1$ gives: $1 - \frac{z^2}{…}$.

In this example you can reasonably easily work out how to solve the problem without recursion by noticing that you calculate the last term that you want first; however, this requires you to think backwards. It also results in code that no longer looks like the algebraic expression, meaning you should comment the code well to explain what you’ve done. The result of avoiding recursion is that you’ve had to do more thinking, the code no longer looks like the calculation, and the next person who looks at your code will find it harder to work out what you’ve done.

Solving this problem recursively looks like this:

This looks a lot like the original equation and is calculated in the same order as you read the equation in.

### Working Through a recursive problem

On another occasion on StackOverflow there was a question (probably either a homework or interview question) asking for the fastest way to print all of the combinations of 4 numbers between 1 and 9 that add to give 20. The answers to this question were fairly practical, such as checking every combination of numbers and seeing which of them added to 20 and scrapping the rest. In a comment, I suggested that you could use a recursive solution to only iterate over the values that actually added to give 20. Here’s how you go about thinking of such a solution:

The first thing to do is to choose a starting value; since we’re likely going to have to iterate through all starting values, either 1 or 9 would be a good choice. Let’s start with 1. We remove 1 from 20, and we get a new but very similar problem i.e. we will then need to find all of the combinations of three values between 1 and 9 that add together to give 19. Being able to reduce the problem to an almost identical but slightly simpler problem is a sure sign that recursion is a good approach. So, if we construct a function that allows us to calculate all the combinations of “n” values that add to “x” then it can do all of the work for both of these cases (e.g. in the first case above “n” is 4 values and x is the number 20, in the second case “n” is 3 and “x” is 19). As a result, we’d expect our function definition to look like this:

We need the `foundVals`

variable to keep track of all the numbers that
we’ve already decided that we’re going to use, i.e. before calling the next
`findAllCombinationsOfNValuesWhichAddToX`

we need to have added a number
to the `foundVals`

string. `foundVals`

will eventually contain the four
numbers separated by a comma and a space in a C string so when we start,
`foundVals`

needs 11 chars of space. For each of the first three
numbers 3 chars are required (the number, a comma, and a space), then we
need the final number and the string terminator.

This is most of the work done (which is one of the lovely things about
recursion). In the simplest form, the solution works like this; we iterate
over all of the numbers that we can subtract from `x`

(i.e. 1 - 9), on each
iteration we write down the value (put it in a string), then we find all
the combinations of `n - 1`

numbers that add to give `x - iterationValue`

. We
stop and print our result when `n`

gets to 1 if our final value is between
1 and 9.

Now we have something that works (well kind of). The current solution has two major problems. The first is that we’re still iterating over all the possible combinations (a problem we hopped recursion would help us with), and the second is we get duplicate values (e.g. we find the value 5, 5, 4, 6 and 5, 5, 6, 4 which aren’t unique solutions).

To solve these issues we need to be more intelligent about which values
we iterate over. So in the `for`

loop let’s remove the hard coded `1`

and
`9`

and replace them with variables `minValue`

and `maxValue`

.

Looking at `minValue`

first, there is a limit on how small `minValue`

can be.
Imagine that we had two values that need to add to 16, now we know that
the largest value that we can use is 9 so the smallest value we can use
is 16 - 9. if you choose any value smaller than this you aren’t able to
make 16. Another example would be 3 values
that add to 20. The maximum that each of the next two values can be is 9 so
the smallest viable value we can choose is 20 - 2 * 9 = 2. In general
the smallest value that we can choose is `x - (n - 1) * 9`

. If this value
is less than 1 then we can go back to the minimum value of 1. This gives
us code like this:

Now we can use the same reasoning to get a maximum value. If
we need two values that sum to 8 then the largest value that we should choose
is `8 - minValue`

. Any value larger than this and we will get a total greater
than 8. Similarly, if we have n values that add to x then the `maxValue`

will be `x - (n - 1) * minValue`

. This gives code that
looks like this:

Putting this together gives:

Note that we can now use our original method of checking whether we should print the values to make sure that our new method is working (i.e. that we aren’t iterating over values that don’t add to x). We should never get to the end of the recursion without a set of numbers that add to x.

So with the recursion we’re now only looping over values that will genuinely
add to x and all other values will be ignored. The only remaining issue is
duplicates. This issue is resolved by noticing that once we’ve found all of the
combinations that have a `1`

, we never need to include `1`

again. What this
means in practice, is that after we’ve iterated over a value, we want
to tell the following calls to the recursive function not to use this
value again. As our iterative values are increasing, we can do this by
passing a minimum value into the recursion instead of assuming that
the minimum value is 1. This leads to the final code looking like this:

Once you’re accustomed to considering a recursive solution, many problems become simpler, shorter, and easier to understand.