Recursively find all coin combinations that produces a specified amount

Question

My apologies in advance. I'm aware that this question has been asked before with answers that have not produced the results I want/need. I am making an attempt to write a function that does the following in Python3:

I need a recursive function that returns all the number of ways (coin combinations) that produce a specified amount. This function can only contain two arguments, amount and coins. I've had a difficult time wrapping my mind around recursion, so explanations would also be greatly appreciated. Thanks.

Here's what I currently have:

COINS = dict(
    USA=[100, 50, 25, 10, 5, 1],
    AUSTRALIA=[200, 100, 50, 20, 10, 5],
    UK=[500, 200, 100, 50, 20, 10, 5, 2, 1]
)

def change(amount, coins):
    """
    >>> change(100, COINS['USA'])
    293
    """
    if amount < 0:
        return 0
    elif amount == 0:
        return 1
    else:
        biggestcoin, *rest = coins[0], coins[1:]
        return change(amount-biggestcoin, coins) + change(amount, rest)

Scruggs

Try searching for the change making problem. The wikipedia page has a lot of good information on it. – Armrest

@others OP has the right idea for the basic algorithm. OP: you should try to debug these things (try using print to determine what variables hold at various points, to confirm that it's what you expect), and when you're asking about something that doesn't work, you should describe how it failed (e.g. include exception tracebacks). – Marseillaise

You have some very basic errors in your code - not difficult to debug with a few prints. As @KarlKnechtel noted, you have the right idea for the algorithm. There is one case that you are missing that might help you out here (I'm going to leave it slightly cryptic because I suspect this is homework): change(amount-biggestcoin, coins). Also, I'm not sure if you are open to other types of recursion, like recursive descent – Pareira

It is homework. I'm new to Python and I've been going through it quite some bit already. – Scruggs

Answer 1

biggestcoin, *rest = coins[0], coins[1:]

You want rest here, logically, not *rest, because you have two items on each side. Using *rest here creates an additional layer of list wrapping, which then results in the exception you're presumably seeing.

Once you fix that: think about what happens if you cannot make the desired amount with 1 of each coin. The change(amount, rest) recursive call will eventually occur with amount being greater than zero, and rest being empty. You need to handle that case as well.

Marseillaise

This is such a nice syntax of Python 3.x, want. – Thumbnail

Having the * syntax for tuple unpacking is nice, but as noted it's not actually desired here :/ – Marseillaise

Answer 2

The idea behind recursion is simple:

Try and reduce the size of the problem, one little step at a time.

If you can do that, you're nearly done! Start with the big problem and just keep reducing the size, little by little, until you end up with a very small problem. You can solve that however you like.

---

How does this apply to the change making problem? Well, if you're asked to make n, you can reduce the size of the problem a little bit by using just one coin. And if you keep going, eventually you will get to a sufficiently-small problem to solve!

Senescent