Changing Money Recursively

Since the greedy solution used by Roman cashiers to solve the Change Problem is incorrect, we’ll consider a different approach. Suppose you need to change 76 denarii, and you only have coins of the three smallest denominations: Coins = (5, 4, 1). A minimal collection of coins totaling 76 denarii must be one of the following:

• a minimal collection of coins totaling 75 denarii, plus one 1-denarius coin;

• a minimal collection of coins totaling 72 denarii, plus one 4-denarius coin;

• a minimal collection of coins totaling 71 denarii, plus one 5-denarius coin.

Recurrence relation

For the general denominations Coins = (coin$_{1}$, … , coin$_{d}$), MinNumCoins(money) is equal to the minimum of d numbers:

$$MinNumCoins(money) = min \begin{Bmatrix} MinNumCoins(money-coin_{1}) + 1 \\ . \\ . \\ MinNumCoins(money-coin_{d}) + 1 \end{Bmatrix}$$

We have just produced a recurrence relation, or an equation for MinNumCoins(money) in terms of MinNumCoins(m) for smaller values m.

Recursive change

The above recurrence relation motivates the following recursive algorithm, which solves the Change Problem by computing MinNumCoins(m) for smaller and smaller values of m. In this algorithm, |Coins| refers to the number of denominations in Coins. See DETOUR: The Towers of Hanoi to get a flavor of recursive algorithms.

RecursiveChange(money, Coins)
   if money = 0
     return 0
   MinNumCoins ← ∞
   for i ← 0 to |Coins| - 1
     if money ≥ coini
       NumCoins ← RecursiveChange(money − coini, Coins)
       if NumCoins + 1 < MinNumCoins
          MinNumCoins ← NumCoins + 1
   return MinNumCoins

STOP and Think: Implement RecursiveChange and run it on money = 76 with Coins = (5, 4, 1). What happens?

RecursiveChange may appear efficient, but it’s completely impractical because it recalculates the optimal coin combination for a given value of money over and over again. For example, when money = 76 and COINS = (5, 4, 1), MinNumCoins(70) gets computed six times, five of which are shown in the figure below. This may not seem like a problem, but MinNumCoins(30) will be computed billions of times!