Counting Change

I’m teaching The Beauty and Joy of Computing (CS 10) this summer for Dan Garcia at UC Berkeley, which has been really fun. One of the big ideas about programming in the course is recursion (the other two being abstraction and higher-order functions). In addition to the programming exercises, we also look at how bigger systems/industries work, current research, and the social implications of all this technology. I love that Dan and the other CS 10 developers included all of this in the introductory course!

But this is a story about recursion. One of the examples we present is taken straight from SICP: the number of ways to make change for some amount of money, given a list of coin denominations.

For example: How many ways can you make change for a dollar given the typical US coins (penny, nickel, dime, and quarter)?

I like showing this because, unlike the straightforward translation of an inductive definition (such as factorial or Fibonacci), this problem isn’t obviously recursive on its face. It actually requires a bit of trick thinking to see how the usual process of dividing the problem, invoking the function, and the combining the results can lead to the solution. It feels a bit closer to the reality of an application than, say, “What’s the 15th Fibonacci number?”

Another great thing about this problem (and one entry point to finding the solution) is that the function has two parameters: the amount of money and the list of coins. Assuming we don’t have the same powers of instant insight that Abelson and Sussman possess, we can still start by reasoning that we must need to make the problem smaller by adjusting one or both of those parameters. That hint — gleaned just by reasoning in general about recursion — is enough to get started down the right path. I won’t spoil it for you if this is the first time you’ve seen this problem, but the solution is given in SICP if you want it.

Visualizing a tree of the solution shows some obvious inefficiencies dealing with pennies. The path that leads to a 100-penny solution for a dollar includes 200 recursive calls just to arrive at a conclusion that probably was obvious: Given only pennies to use, there is exactly one way to make a dollar. I pointed this out in the lecture and left it at that. But one of my students came up after class to ask about it and I encouraged him to try to optimize the solution. The next week at office hours, he brought in his code and we ended up in a very interesting discussion.

Among the questions posed: Are there more optimizations to be made beyond pennies? Can we generalize those optimizations? Have we biased our understanding of the problem by focusing on solving for amounts that are multiples of 5 or 10 cents (when we have nickels and dimes to use)? What if there’s no penny-type coin? What if none of the coin values are multiples of each other? A pathological currency indeed that uses prime coin values. What does an iterative solution look like? And so on.

This student went away and worked on it again, reporting back that he had an iterative solution based on decomposing the amount and substituting smaller denomination combinations, but that it over-counted solutions by calculating the number of permutations instead of combinations. What a perfect motivation for investigating the relationship between the two! And all of this from a simple puzzle-type question with a clever recursive solution.

Maybe this kind of delving is normal at the university level, but I find it quite refreshing coming from the high school teaching experience. I like that this inquiry can be self-directed: the student certainly didn’t need to dive into this problem, but everyone needs to dive into some problem at some point. And yet, without some support that dive can become aimless or overwhelming very quickly. This provides one answer to the question, “Why not just take the course by watching videos?” We real-life real-time teacher people still provide value in supporting and engaging an individual learning path. That is something that I don’t see changing, even as the educational enterprise follows the technology trends of our day.

(photo credit: adam*b, remix via obamicon.me)