sponsors gamedev.net search:

Counting change As we saw, it isn't hard to come up with a simple iterative Fibonacci algorithm (the same goes for the factorial function, another common example of recursion in programming books and tutorials). In contrast, consider the following problem: How many different ways can we make change of $1.00, given half-dollars, quarters ($0.25), dimes ($0.10), nickels ($0.05), and cents ($0.01)? More generally, can we design an algorithm to compute the number of ways to change any given amount of money? While at first sight an innocuous problem that might interest supermarket cashiers, this is a close relative of an important algorithm - the subset sum problem (once again, google can be your guide to enlightenment). Let's start with an example, to make sure that the problem is understood. In how many ways can we make change from 10 cents? One is ten cents. Two is one nickel and five cents. Three is two nickels. Four is a dime. So, there are four ways. In fact, this problem has a simple recursive solution. Suppose we think of the types of coins available as arranged in some order. Then the following relation holds: The number of ways to change amount a using n kinds of coins equals the number of ways to change amount a using all but the first kind of coin, plus The number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first coin. Rationale: note that given a task to make change, we can divide it to two complementary groups: ways that don't use the first kind of coin, and ways that do. The total number of ways is the sum of those two groups - that is, the number of ways to make change without using the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. But if we've used the first kind, what remains is the amount minus the denomination of the first kind. Thus, we've found a way to solve the problem by reducing it to two smaller problems (in the first the amount of coins is smaller, and in the second the sum is smaller). This is just what recursion is about - reducing problems to simpler problems. What we're lacking is an explicit solution for the "simplest" problems: If the amount a is 0, there's only one way to make change (no coins) If the amount a is negative, there is no way to make change If n is 0, there's only one way to make change (we don't have any choice...) To convince you that the reduction and boundary cases work, lets look again at the 10 cent problem (note that we're not interested in 25 and 50 cent coins in this case): So, to change 10 using the coins 10, 5 and 1 (ordered thus) we sum (1) the number of ways to change 10 using all but the first kind of coin, that is using 5 and 1 only, and (2) the number of ways to change amount 10 - 10 = 0 using all kinds of coins. (2) Is simple - there's one way to change amount 0 (by the first boundary case). (1) can be further reduced to (3) the number of ways to change amount 10 using 1 cent only, plus (4) the number of ways to change 10 - 5 = 5 using all kinds of coins. (3) Is only one way, ten 1 cent coins, (4) can be reduced, etc. (we get two ways from (4) - one five cent coin, and five one cent coins). When the algorithm finishes we'll end up with 4 ways. To take care of the coins ordering, we'll define a helper function: long first_denomination(long n_kinds_of_coins) { switch (n_kinds_of_coins) { case 5: return 50; case 4: return 25; case 3: return 10; case 2: return 5; case 1: return 1; default: assert(0); } } Given how many coins we can use, this function returns the denomination of the first coin. It sets up the following ordering of the coins - 50, then 25, then 10, then 5, then 1. Now we're ready for to implement the change counting procedure itself. As a true recursive algorithm, it translates into code very naturally: long count_change_aux(long amount, long n_kinds_of_coins) { if (amount == 0) return 1; else if (amount < 0 || n_kinds_of_coins == 0) return 0; else { return count_change_aux(amount, n_kinds_of_coins - 1) + count_change_aux(amount - first_denomination(n_kinds_of_coins), n_kinds_of_coins); } } long count_change(long amount) { return count_change_aux(amount, 5); } count_change is the procedure that is to be called to get an answer, and it uses count_change_aux as a helper function. If you understood the algorithm and the boundary cases, there's really not much left to explain, since the code is just the algorithm "paraphrased" (to be exact, written in another language - C++ instead of English). On to some benchmarking: count_change answers our original question (how many ways are there to make change of a dollar) in a no-time - below resolution of system clock (the answer is 292, by the way). However, when we start raising the stakes the runtime grows quickly. It takes 5 seconds for 1000 cents, 2.5 minutes for 2000 and the time soars rapidly on and on. Care to throw a guess at the cause of this slowness? Right - it's the same problem we had with fib_rec - multiple repetitions of the same calculations. To get some intuition of the problem, suppose that we run count_change on 2000 cents. Consider an intermediate sum of 1000 cents. How many ways are there to reach 1000 cents from 2000 cents? Quite a lot... But each time we reach 1000 cents we go on and compute the ways to change 1000 cents, and we saw that it takes 5 seconds each time - so it's not surprising that the runtime grows so quickly. Contrary to the Fibonacci problem, here we don't have any simple way to formulate a swift iterative algorithm that will complete the same task (if you find one, let me know!). But we'd still like to compute change for large sums in a reasonable time. The solution is memoization. Memoized change counting We will proceed in a manner similar to the memoization of fib_rec: we'd like to keep the results of count_change_aux computations in some cache and return immediately with a cached result when requested to do some computation for the second time. The only slightly problematic point is that we can't just use a simple array for the cache as we did in fib_memoized, since count_change_aux takes two arguments. However, as this code demonstrates; there's really no problem expanding the memoization technique to use multiple arguments. long count_change_memoized_aux(map<pair<long, long>, long>& cache, long amount, long n_kinds_of_coins) { pair<long, long> entry = make_pair(amount, n_kinds_of_coins); if (cache.find(entry) != cache.end()) return cache[entry]; if (amount == 0) cache[entry] = 1; else if (amount < 0 || n_kinds_of_coins == 0) cache[entry] = 0; else { cache[entry] = count_change_memoized_aux(cache, amount, n_kinds_of_coins - 1) + count_change_memoized_aux(cache, amount - first_denomination(n_kinds_of_coins), n_kinds_of_coins); } return cache[entry]; } long count_change_memoized(long amount) { map<pair<long, long>, long> cache; return count_change_memoized_aux(cache, amount, 5); } Note that first_denomination remains the same as in the simple recursive version, so I didn't reproduce it here. Here I use a map as the cache. It maps argument pairs to results: for a pair of (amount, n kinds of coins) the cache holds the number of ways to change this amount with this number of kinds of coins. Except for the different data structure used as a cache, the changes are very similar to the ones in fib_memoized - first of all the cache is consulted and if the desired result is already there it's simply returned. Then, the real calculation is performed and added to the cache. The next time the function runs with the same arguments - the computation will be immediate - simply a fetch from the cache. And indeed, benchmarking shows considerable speed improvement. Change from 2000 cents now takes only 0.02 seconds to compute (vs. 2.5 minutes for the non-memoized version). Change from 5000 takes 0.06 seconds (I gave up waiting for the non-memoized version to finish this calculation). The runtime increase for the memoized version increases linearly with the size of the problem - as expected. Wrapping up In this article you've been introduced to memoization - an important programming technique used to speed up computations. In particular, memoization often allows one to considerably improve the runtime of a crawling recursive algorithm that may be just the right solution for a problem but is too slow to use. You learned about the inherent slowness in some recursive computations due to repetitions, and saw how to use memoization to eliminate this problem. You probably noticed the similarity between memoizing the Fibonacci implementation and memoizing the change counting algorithm. Indeed, memoization is quite simple to apply automatically, if the programming language allows it. For example, in Lisp where functions are data just like any other data, memoizing an arbitrary function is trivial. In Perl it is a little bit trickier, but there exists an excellent module called Memoize that will automatically memoize any function for you. As far as I know there is no simple way to achieve this in C++.

Contents   Recursion   Memoized Fibonacci   Counting change   Printable version   Discuss this article The Series   Part 1   Part 2   Part 3   Part 4   Part 5   Part 6   Part 7   Part 8