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:

// `i` is the iteration of the recursion and `n` is
 //  just for testing when we should end. 'zz' is z^2
double theRestOfTheContinuedFraction (double zz, int i, int n) {
  if (!n)
    return 1;
 
  return 2 * i - 1 - i * i * zz / theRestOfTheContinuedFraction (zz, i + 1, n - 1);
}
 
double contFracLog (double z, int n) {
  return 2 * z / theRestOfTheContinuedFraction (z * z, 1, n);
}

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:

// x is the value that we need to sum to, and n is the number
 //  of values (between 1 and 9) that we can use to add to get x.
void findAllCombinationsOfNValuesWhichAddToX (int n, int x, char *foundVals);

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.

// x is the value that we need to sum to, and n is the number
 //  of values (between 1 and 9) that we can use to add to x.
void findAllCombinationsOfNValuesWhichAddToX (int n, int x, char *foundVals) {
  if (n > 1) {
    // Let's iterate over all of the numbers that we could subtract from x,
    // subtract these values from x, and then find all combinations of
    // numbers that can sum to give the new value (keeping track of
    // numbers that we've used in foundVals).
    for (int i = 1; i < 9; ++i) {
      // First append the value that we've chosen to the string.
      int origStrLen = strlen (foundVals);
      char appendStr[4];
      sprintf(appendStr, "%d, ", i);
      strcat (foundVals, appendStr);
      // Now work out the rest of the values that we need to add to get to the
      // remaining number.
      findAllCombinationsOfNValuesWhichAddToX (n - 1, x - i, foundVals);
 
      // Remove the value that we chose this time round ready to
      // append a new value next time round.
      foundVals[origStrLen] = '\0';
    }
    return;
  }
 
  if (x > 9 || x < 1)
    return;
 
  // We've found a group of numbers that adds to 20.
  printf ("%s%d\n", foundVals, x);
}

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:

int minValue = x - (n - 1) * 9;
if (minValue < 1)
  minValue = 1;
 
for (int i = minValue; i < 9; ++i) {
...

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:

int maxValue = x - (n - 1) * minValue;
  if (maxValue > 9)
    maxValue = 9;

Putting this together gives:

// n is the value that we need to sum to, and x is the number
 //  of values (between 1 and 9) that we can use to add to n.
void findAllCombinationsOfNValuesWhichAddToX (int n, int x, char *foundVals) {
  if (n > 1) {
    // Let's iterate over all of the numbers that we could subtract from n,
    // subtract these values from n, and then find all combinations of
    // numbers that can sum to give the new value. (keeping track of
    // numbers that we've used in foundVals).
 
    int minValue = x - (n - 1) * 9;
    if (minValue < 1)
      minValue = 1;
 
    int maxValue = x - (n - 1) * minValue;
    if (maxValue > 9)
      maxValue = 9;
 
    for (int i = minValue; i < maxValue; ++i) {
      // First append the value that we've choosen to the string.
      int origStrLen = strlen (foundVals);
      char appendStr[4];
      sprintf(appendStr, "%d, ", i);
      strcat (foundVals, appendStr);
      // Now work out the rest of the values that we need to add to get to the
      // remaining number.
      findAllCombinationsOfNValuesWhichAddToX (n - 1, x - i, foundVals);
 
      // Remove the value that we chose this time round ready to
      // append a new value next time round.
      foundVals[origStrLen] = '\0';
    }
    return;
  }
 
  if (x > 9 || x < 1) {
    printf ("There's something wrong with the code we should never get here");
    exit (0);
  }
 
  // We've found a group of numbers that adds to 20.
  printf ("%s%d\n", foundVals, x);
}

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:

// n is the value that we need to sum to, and x is the number
 //  of values (between 1 and 9) that we can use to add to n.
void findAllCombinationsOfNValuesWhichAddToX (int n, int x, char *foundVals,
                                              int minValue) {
  if (n > 1) {
    // Let's iterate over all of the numbers that we could subtract from x,
    // subtract these values from x, and then find all combinations of
    // numbers that can sum to give the new value. (keeping track of
    // numbers that we've used in foundVals).
    int newMin = x - (n - 1) * 9;
    if (newMin < minValue)
      newMin = minValue;
 
    int maxValue = x - (n - 1) * minValue;
    if (maxValue > 9)
      maxValue = 9;
 
    for (int i = newMin; i <= maxValue; ++i) {
      // First append the value that we've chosen to the string.
      int origStrLen = strlen (foundVals);
      char appendStr[4];
      sprintf(appendStr, "%d, ", i);
      strcat (foundVals, appendStr);
      // Now work out the rest of the values that we need to add to get to the
      // remaining number.
      findAllCombinationsOfNValuesWhichAddToX (n - 1, x - i, foundVals, i);
 
      // Remove the value that we chose this time round ready to
      // append a new value next time. */
      foundVals[origStrLen] = '\0';
    }
    return;
}
 
  if (minValue > x) {
    // This deals with a single edge case where choosing the maxValue in
    // the iteration can leave you with n as maxValue - 1, which would 
    // print a combination that has already been found (e.g. two numbers
    // that add to give 17, first we get 8, 9, then when we do the next
    // iteration we'd choose 9, first leaving n as 8, and end up here).
    return;
  }
 
  if (x > 9 || x < 1) {
    printf ("There's something wrong with the code we should never get here");
    exit (0);
  }
 
  // We've found a group of numbers that adds to 20.
  printf ("%s%d\n", foundVals, x);
}

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