In an old Saturday Night Live, there was a fake ad for a bank that specialized in making change. That's all they did, but they were very good at it.
You have been hired by this fictitious bank to write a program for them that counts the number of possible ways to make change for a given amount of money. Let's assume that we are dealing with coins only and not concern ourselves with paper money.
Ultimately, you want a method that takes two arguments:
In addition, the following information is available in a class variable:
Thus the invocation countChange (100, 5) would ask how many ways there are make change for a dollar, using pennies, nickels, dimes and quarters and half-dollars. The answer is 292.
WARNING: This question is hard. I want you to think about it because it is worth thinking about. Even if you don't come up with an optimal answer, the process of thinking about it will be valuable.
So try not to be frustrated by the difficulty of the problem; try to enjoy the process of thinking about it.
CREDIT: This problem is taken from Abelson and Sussman, Structure and Interpretation of Computer Programs, MIT Press, 1987.