# Solving recursively with no permutations - represent N cents with infinite number of quarters

Hi,
Im trying to solve the following problem: “Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents”

I have (perhaps) a naive implementation with a recursive algorithm, given below:

``````public static int nCents(double amount) {
if (amount == 0)
return 1;
int count = 0;
if (amount - 25 >= 0)
count += nCents(amount - 25);
if (amount - 10 >= 0)
count += nCents(amount - 10);
if (amount - 5 >= 0)
count += nCents(amount - 5);
if (amount - 1 >= 0)
count += nCents(amount -1);
return count;
}
``````

I believe its good, but It gives me also similar number of coins, but with different permutations,
for the value 7, i.e, i may take into account 1 + 1 + 5, 1 + 5 + 1, 5 + 1 +1, all of which are the same for me.
How can I tweak it a bit in order to ignore it, efficiently?

First observation - you do not need double as amount, right? If you want to skip those similar permutation implement logic with this idea:

If you select X coints in step i, you cans select in step i+1 only bigger or equal/lower or equal value (depends on your choice)

So at the end you will have `5 1 1` or `1 1 5` permutation only.

What is the max value of `amount`? Because you algorithm is naive - it returns correct value, but will be slow even for n = 100 or so, try it. It is similar as with fibonacci if you know what I meant…