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

general
1

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?

2

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…