Recursive Money Counting: Or why avoid recursion

Last post I asked this:

Question: Write an algorithm that, when given some number of pennies, will print out all the ways that this value can be represented in nickels, dimes, quarters, and dollars, but don't use recursion.

In this post, I'm going to describe the recursive version and then talk about some of the differences between the two.

As mentioned, I don't much like recursion because of the overhead and because it makes things like ugly in a debugger.

But it does often lead to easier to develop and maintain code. It is, after all, just using another construct of a high level language, like objects or inheritance or function overloading. Those all have costs, but we happily pay them because it tends to make our software faster to develop and easier to maintain.

But here is the big difference in my mind: recursion is used most obviously in the design of the algorithms we most want to execute quickly: sorting, tree traversal, etc.

Algorists tend to love recursion because it makes for tidy algorithms (think quick sort, then try to imagine it without recursion: doable, but really ugly and no good for a text book). But algorithm design is exactly where you want to pay attention to performance issues. After all, if you just wanted easy to understand algorithms, we'd all just use insertion sort or bubble sort in all cases and be done with it and we certainly wouldn't worry about using adaptive sorting algorithms.

What is the cost of recursion? Well each time we call a function, we create a stack frame with the byte code we're executing and any local variables and parameters, then we push the frame onto the stack. When we return, we have to pop that frame off the stack restore the local variables and parameters and jump back to the byte code we were executing before we started. People who write JVMs and compilers care a bunch about making this run fast, but the fastest code is the code you don't execute so it'll always take some time. How much? Lets run through the recursive method and do some comparisons to find out.

For the recursive version of this algorithm, I'm going to leave out the printCurrency and getValue they are identical to the versions in the last post if you want to see them.

  public static void startRecursiveCountPennies(int pennies) {
      int[] mInts = {0,0,0,0};
      recursiveConvertPennies(pennies, mInts, mInts.length -1);
  }
  public static void recursiveConvertPennies(int pennies, int[] currency, int currencyTypeIndex) {
      while(true) {
          if(getValue(currency) > pennies) {
              currency[currencyTypeIndex] = 0;
              return;
          }
          if(currencyTypeIndex == 0) {
              printCurrency(pennies, currency);
          } else {
              recursiveConvertPennies(pennies, currency, currencyTypeIndex - 1);
          }
          currency[currencyTypeIndex]++;
      }
  }

So what is happening here? We're creating an array to represent the total number of each type of coin (except pennies, remember we just calculate how many pennies are left over for each of the coin type sets) and we're using a pointer to indicate where in the array we are working. While the value of our currency array is less than the total number of pennies, we call increment the counter and call ourselves, then increment the number of the type of currency the pointer is pointing at, and so on.

Before we return, we reset the currency type at our pointer to zero.

When the pointer itself is zero we'll print the values rather than calling ourselves again.

As a test, I commented out the printing of the values, set some timers and ran both the recursive and the non-recursive methods with 5000 pennies each. Over and over again, the nonrecursive version ran 20% faster than the recursive version.

So there you have it. Later on, I'll write a post about the recursive vs. non-recursive string mutation method. To be titled: how I didn't get a job I wanted back in 2001.

Take home lesson:

Recursion may make for easy to read algorithms, but be mindful of the costs.