Hi there. I was looking for some help, mainly with the thought process that is involved with writing a program that takes an int input and returns the number of ways change can be made from that input using dollars, quarters, dimes, nickels, and pennies. I would like to solve this using recursion. Right now the idea I have involves seeing how many dollars goes into the input, using the remainder I can then see how many quarters go in, remainder of that see how many dimes go in, and so on down the line. Then the next time through do it with one less dollar until I'm using 0 dollars, then with quarters until I'm using 0 quarters, etc. etc. As I'm writing this I suppose the issue I'm having is turning my thoughts into code, but I'm also confused as to how to keep track of and decrement the amounts using recursion. Any help is very much appreciated.
I'll try to clarify. I'm trying to get the total number of ways change could be given, given an input in pennies. I.e. input of 107 ($1.07) could be given in change as:
1 dollar
0 quarters
0 dimes
1 nickel
2 pennies
Or
0 dollars
4 quarters
0 dimes
1 nickel
2 pennies
and so on down the line, simply keeping track of the vast number of ways change could be given for that amount.
I've been making attempts using nested for-loops but always seem to run into issues. Here's an example of what I'm working on.
Sometimes it helps to start with the data that you need. You need the number of coins/bills that you're making change with. And their values and names:
For a recursive solution, you need to keep track of the change in your partial solution, along with how much change you still need to give. Here is a partial solution. The hard part is described in the comments at the bottom. Can you figure out how to do that part?
// Print all the ways to make amt in change. The change array
// contains coins already in hand. The job of this function is to
// make change for amt, using the coins whose index is idx or greater.
// returns the number of combinations
int makeChange(int amt,
unsigned change[NumCoinTypes],
unsigned idx)
{
int result = 0;
// For debugging, print the values in this call
cout << "makechange(" << amt << ',' << idx << ")\n";
// error checking
if (amt < 0 || idx >= NumCoinTypes) {
cout << "Error\n";
result = -1;
} elseif (amt == 0) {
// Yeah! No more change to make. Print out what you have
for (unsigned i = 0; i < NumCoinTypes; ++i) {
cout << change[i] << ' ' << coinNames[i] << ' ';
}
cout << '\n';
result = 1;
} elseif (idx == NumCoinTypes-1) {
// You're down to pennies. Add all pennies to the change, then
// Call yourself recursively to print it out
change[idx] += amt;
result = makeChange(0, change, idx);
// Now remove the change you added to restore the previous value.
change[idx] -= amt;
} else {
// You can add up to "maxNum" coins of the current value
unsigned maxNum = amt / coinValues[idx];
for (unsigned i = 0; i <= maxNum; ++i) {
// Add "i" coins to the change
// call yourself recursively, asking for the new amount of change, and
// telling the recursive call to add the next type of coin.
// Remove "i" coins from the change to restore it to the previous value
}
}
return result;
}