Decompose an amount using recursion

Question

Given the array

bills = [500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01].

It is asked to write a function decompose()that will decompose an amount in bills that are contained in the array.

For example decompose(423) will return a list containing the following elements

[200, 200, 20, 1, 1, 1]

This is my code:

bills = [500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]

def decompose(amount, lst = []):
    if len(bills) == 1:
        return lst

    if amount > bills[0]:
        lst += [bills[0]]
        amount = amount - bills[0]
        return decompose(bills, lst + [bills[0]])
    return decompose(bills[1:], lst + [bills[0]]) 

print(decompose(523))

My output is:

Traceback (most recent call last):
  File "test.py", line 94, in <module>
    print(decompose(523)) 
  File "test.py", line 91, in decompose
    return decompose(bills, lst + [bills[0]])
  File "test.py", line 88, in decompose
    if amount > bills[0]:
TypeError: '>' not supported between instances of 'list' and 'int'

How do I do decompose my amount?

Google *change making*. – meowgoesthedog Dec 19 '18 at 19:02 — meowgoesthedog, Dec 19 '18 at 19:02

score 4 · Accepted Answer · answered Dec 19 '18 at 19:02

You should recursively deduct the bill value from the amount when the top bill fits the amount, or recursively move on to the next bill while keeping the same amount instead:

def decompose(amount, bills):
    if not bills:
        return []
    if amount >= bills[0]:
        return [bills[0]] + decompose(amount - bills[0], bills)
    else:
        return decompose(amount, bills[1:])

so that:

bills = [500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]
decompose(423, bills)

returns:

[200, 200, 20, 2, 1]

Patrick Artner · Answer 2 · 2018-12-19T19:19:39.073

You are trying to supply the bills in place of the current amount - and hence later you get the error because you can not do amount >= bills[0] for list and int.

There are several other errors in your code:

def decompose(amount, bills, lst = None):  # fix here - supply the possible bills as well
    lst = lst or []
    if amount == 0:                      # fix - when amount == 0 you are done
        return lst

    if amount >= bills[0]:      # fix - as long as bills[0] can be deducted, do so (>=)
        lst += [bills[0]]       # bill[0] is already addded no need to do below again
        amount = amount - bills[0]
        return decompose(amount, bills, lst ) # fix - supply same bills, 
    return decompose(amount, bills[1:], lst ) # fix - bill[0] too big, supply bills[1:]

bills = [500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]
print(decompose(523, bills))

Output:

[500, 20, 2, 1]

You might want to look into debugging: https://wiki.python.org/moin/PythonDebuggingTools stepping through your code helps immensely - after some time you develop an internal debugger for small code pieces like this ;o)

Note that using a mutable object as a default value will produce incorrect result when the function is called more than once. — blhsing, Dec 19 '18 at 19:04
[least-astonishment-and-the-mutable-default-argument](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument) would be the relevant dupe for my error :) — Patrick Artner, Dec 19 '18 at 19:22

Decompose an amount using recursion

2 Answers2