Recursion in C++ : The Coin Changing Problem

Let’s say that we have an infinite supply of pennies ( 1 cent ), nickels ( 5 cents ), dimes (10 cents ) and quarters (25 cents). (That would probably be a nice thing — having an infinite number of coins, whatever be the denomination. On a different note, the fact that this question assumes such an infinite supply of coins should convince everyone of the hypothetical nature of this and similar problems. That said, it is sometimes useful to get a fair idea of how to go about solving seemingly contrived problems in order to tackle realistic ones.)

Coming back to the problem — We buy a commodity and are required to pay n cents for it. Now, the interesting bit is that we are required to pay exactly n cents, i.e. we cannot pay more and get change in return. So, the question is — How many ways can we possibly pay n cents using our infinite supply of coins?

The question could be rephrased thus:

Given the equation: n = x + 5 y + 10 z + 25 w where x, y, z, w are non-negative integers, find the total number of possible solutions to the equation.

——-

Let’s take an example to clarify things — say. n = 91.

Let f (n) denote the number of ways n can be represented in terms of coins having denomination 1, 5, 10 and 25.

Thus, our task is to compute f(91).

The coin of the highest denomination is that of 25 cents.

We have 2 choices before us: (1) use at least one 25-cent coin, or  (2) do not use 25-cent coins at all.

f(n) is the sum of the number of ways we can perform (1) and (2).

(1) If we decide to use at least one 25-cent coin:

We can see that we can use either 1, 2 or 3 such coins.

If we use 1 25-cent coin, we are left with 66 cents to be represented using coins of denominations 1, 5 and 10. So, we now see that we have a smaller subproblem — that of representing 66 cents using 1, 5 and 10 cent coins.

We digress here to make a remark about notation.

—-

Let us denote by f(n, k) the total number of ways in which we can represent n cents using coins of denomination \leq k with the added condition that at least 1 coin of denomination k is used.

Thus, we have that f(n) = f(n, 25) + f(n, 10) + f(n, 10) + f(n, 1).

(The 1st term denotes the number of ways we can represent n cents using 1, 5, 10 and 25-cent coins such that at least 1 25-cent coin is used. The 2nd term — f(n,10) denotes the number of ways wherein we do not use any 25-cent coins and use at least 1 10-cent coin. Similarly, we can work out the meaning of the remaining terms. It can be observed that the events represented by each of the these terms are in some sense disjoint, which is why we can simply add these terms to get our desired result.)

——–

Going back to our example, the number of ways we can represent 66 cents using coins of denomination only 1, 5 or 10 cents is equal to f(66,10) + f(66,5) + f(66,1).

—-

We again digress to make another remark on notation.

We use g(n,k) to denote the number of ways in which we can represent n cents using coins of denominations \leq k.

Hence, our original task, which was to compute f(n) is the same as computing g(n, 25).

——–

Again, coming back to the example, we see that the number of ways to represent 66 cents using 1, 5  and 10-cent coins is simply g(66, 10).

Now, what if we decide to use 2 25-cent coins in representing 91 cents. Then, we are left with representing 41 cents using 1, 5 and 10-cent coins, which can be done in g(41, 10) ways.

Similarly, we can see that we can represent 91 cents using 3 25-cent coins in g(16, 10) ways.

—-

A little reflection would get us the following equation:-

g(91, 25) = f(91,25) + f(91, 10) + f(91, 5) + f(91, 1)

= [ g(66,10) + g(41, 10) + g(16, 10) ] + [ g(81, 5) + g(71, 5) + ... + g(1, 5) ] + [ g (86, 1) + g(81, 1) + ... + g(1, 1) ] + [ 1 ].

———

We can now write the method discussed above in the form of a function in C++.

——-

#include <iostream.h>

// Let’s say we have a global array A[4] = {25, 10, 5, 1}.

//func F takes a non-negative input n, and an index into the array A.

// It returns f (n, A[i]) [where the notation f(n,k) is as discussed earlier.]

int F (int n, int index) ;

// func G takes non-negative input n, and an index into the array A, and returns g(n,A[i]) as discussed above.

int G (int n, int index) // the initial call from the main ( ) function would be G(n,0).

{

int i = index;

int ans = 0;

for ( ; i < 4; i++)

ans + = F (n, i);

return ans;

}

//Now we give the implementation of func F.

int F ( int n, int index )

{

if ( n < A[index] )

return 0;

if ( index == 3)

return 1; // because f(n,1) == 1.

int ans = 0, quotient = n/ A[index];

for (int i = 1; i <= quotient; i++)

{

ans + = G (n – i*A[index], index+1)

}

return ans;

}

———

4 Responses to Recursion in C++ : The Coin Changing Problem

  1. raj says:

    awesome article!!
    thnx a lot for this…..this problem looks easy on the surface but it is very complex(thnx to recursion)….
    but u did a perfect job of explaining

  2. sid says:

    nice explanation🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: