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?

Answer 1

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]