The Change-Counting Algorithm & TDD

I recently decided to make my way through Sussman & Abelson's classic CS textbook The Structure and Interpretation of Computer Programs, partly for reasons of professionalism, partly to clarify my thoughts on "test-driven development" and algorithmic programming. Every familiar example, and nearly every question I see on the Test-Driven Development newsgroup concerns object-oriented programming. The "bowling game" is simply too trivial a counterexample, in my opinion, but we can dispute this elsewhere.

At any rate, SICP poses this problem in Chapter 1: "How many different ways can we make change of $ 1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to
change any given amount of money?" There is, it turns out, a fair amount of literature on this problem (cf. David Pearson's paper, or
What This Country Needs is an 18 Cent Piece). Despite having the solution right in front of me, an implementation eluded me until I really considered the structure of the problem, which is recursive. The authors provide unequivocal hints: "Consider this reduction rule carefully, and convince yourself that we can use it to describe an algorithm if we specify the following degenerate cases: 1, If a is exactly 0, we should count that as 1 way to make change; 2, If a is less than 0, we should count that as 0 ways to make change; 3, If n [the number of available denominations] is 0, we should count that as 0 ways to make change." These should be the starting points for the test-driven development of the algorithm, but I only understood their significance within the recursion after pondering the problem while riding the bus. Imagine you've got quarters and pennies, and are asked to make $.26 in change. You can try to use 1 quarter. Now you've got to make $.01 with quarters and pennies. If you use another quarter, you've then got to make - $.24, at which point condition 1 will obtain; if you use a penny, you'll then have to make $.00, at which point condition 2 will obtain (and the recursion will stop). Condition 3 will also stop the recursion, i.e., you've got no more denominations to try. Once I'd understood all this, I could eliminate some of the recursive calls by using integer division, i.e., the largest number of quarters that I can use to make a will be a / 25.

After that, I quickly wrote the following code in Python, and indeed this implementation evolved in order with precisely these tests:

import unittest

def countChange(amount, coins):
    if amount == 0:
        return 1
    if len(coins) == 0:
        return 0
    if len(coins) == 1 and amount % coins[0] == 0:
        return 1
    currentCoin = coins[0]
    remainingCoins = coins[1:]
    currentPossibilities = [currentCoin * i for i in range(0, amount / currentCoin + 1)]
    return sum([countChange(amount - p, remainingCoins) for p in currentPossibilities])

class TestCountChange(unittest.TestCase):
    def testAmountZeroWithNoCoins(self):
        self.assertEqual(1, countChange(0, []))
        
    def testAnyAmountWithNoCoins(self):
        self.assertEqual(0, countChange(100, []))
        
    def testAmountZeroWithAnyCoins(self):
        self.assertEqual(1, countChange(0, (1, 5, 10)))
        
    def testAmountsWithOneCoin(self):
        self.assertEqual(1, countChange(1, [1]))
        self.assertEqual(1, countChange(5, [5]))
        self.assertEqual(1, countChange(10, [10]))
        
    def testAnyAmountWithPennies(self):
        self.assertEqual(1, countChange(10, [1]))
        self.assertEqual(1, countChange(10000, [1]))
        
    def testMultiplesOfSingleCoin(self):
        self.assertEqual(1, countChange(100, [5]))
        self.assertEqual(1, countChange(100, [50]))
        
    def testTwoKindsOfCoins(self):
        self.assertEqual(2, countChange(10, [5, 10]))
        self.assertEqual(2, countChange(7, [5, 1]))
        self.assertEqual(0, countChange(7, [5, 10]))
        
    def testTextbookExample(self):
        self.assertEqual(292, countChange(100, [1, 5, 10, 25, 50]))

if __name__ == '__main__':
    unittest.main()