## The Problem

How many possible ways can you make change for 2£ given the following English coins: 1p, 2p, 5p, 10p, 20p, 50p, 1£ (100p), 2£ (200p)?

One example output would be: 5 x 1p, 5 x 2p, 1 x 5p, 1 x 10p, 1 x 20p, 1 x 50p, 1 x 1£

## Understanding the Problem

This problem deals with the possible permutations of coins that equal 2£. However, it is not a pure combinatorics problem like Rock Paper Scissors because we do not want duplicates (1 x 1p,1 x 2p is the same as 1 x 2p,1 x 1p and therefore we should only count one of these as a possible combinations.)

Let’s start off by looking at a smaller version of this problem. Imagine that we have only 3 different types of coins - 1p, 5p, and 10p - and we’re trying to make ‘piles’ of coins that sum up to 20p. What are the possible coin combinations that we can make?

Number of coins of each type used:

10p - | - 5p - | - 1p |
---|---|---|

0 | 0 | 20 |

0 | 1 | 15 |

0 | 2 | 10 |

0 | 3 | 5 |

0 | 4 | 0 |

1 | 0 | 10 |

1 | 1 | 5 |

1 | 2 | 0 |

2 | 0 | 0 |

There is a pattern here. Looking at the first row of this table, we might think of this problem as starting by looking the largest-valued coin (10p) with 20p value needed to reach the total and adding none of this type of coin, and then looking at the next-largest-valued coin (5p) with still 20p value needed and adding none of this type of coin, and then finally getting to the 1p coin and iterating through to add 20 x 1p coins to reach the total of 20p. Now look at the second row of the table. We look at the largest-valued coin (10p) with 20p value needed to reach the total and adding none of this type of coin, and then looking at the next-largest-valued coin (5p) with still 20p value needed and add one of this type of coin, and then finally getting to the 1p coin and iterating through to add 15 x 1p coins to reach the total of 20p. In Javascript, this pattern looks like it could be represented by a series of nested for loops.

## The Code

Let’s translate this problem into Javascript and write a function called

1 | makeChange |

### Input and Output

The argument of the function is a variable called

1 | total |

1

makeChange

with 200.
The return value is the number of possible ways to make change for the total. This will be represented as a counter named

1 | count |

This gives us the basic structure below:

### To Iterate or to Recurse?

An iterative approach requires that we hard-code each of the type of coins in their own for loop. An iterative solution might look something like the following:

Note that the

1 | coins[coins.length-1] |

The iterative function works but it’s not very elegant. In fact, the coin sums problem can easily be divided into a series of similar subproblems - get all the combinations of coins with just 1p coins, all the combinations with 1p and 2p coins, all the combinations with 1p, 2p, and 5p coins, etc - and a problem like this is perfect for a recursive function.

## The Recursive Function

### The basic structure

We’ll put a recursive subroutine called

1 | changer |

1

makeChange

:
### Arguments

There are two things that we need to keep track of with each call of our recursive function. We’ll want to make these arguments of the recursive function.

First, we need to know which type of coin we’re adding to our pile. In the iterative version, we keep track of this in the decrement at every level of for loops. Here, we’ll use

1 | index |

1

coins

array we’re working with. Second, as we add coins to our pile, we need to keep track of the value still needed to reach the 1

total

. In the iterative version, we do this by initializing the variable in each nested loop to the value of the previous loop (as in var b = a, var c = b, etc.) In this recursive version, we save this information in a variable called 1

valueLeft

and we’ll initially set it to 1

total

.
### Inside the Recursive Function

We’ve already decided that we’ll start with the highest-valued coin and work backwards through the

1 | coins |

1

currentCoin

.
Now that we have

1 | coinsLeft |

1

valueLeft

, and 1

currentCoin

, we can start creating ‘piles’ of coins that add up to 1

total

. We can do this by calling the recursive function with a copy of 1

coinsLeft

and 1

valueLeft

, moving our way deep into the 1

coinsLeft

array just as we moved deep into the nested for loops.
But when do we increment our counter and capture the number of possible ways to reach the total? This is done when the index of

1 | coins |

1

value

needed with the 1

currentCoin

without a remainder). Once we reach this point, we want to return out of the loop.
Putting this all together, we get the final code like below: