0

I'm experimenting with recursive solutions to cash. I've got a number of working solutions but eventually decided I wanted to extend the functionality of the program (just to learn). I tried to write a recursive function that would return a list of the actual denominations used and I could then simply count the number of elements in this list to arrive at the minimum number of coins. For example:

  • an input of 0.15 would result in a list of [10, 5] - 2 coins used.
  • an input of 0.41 would result in a list of [25, 10, 5, 1] - 4 coins etc.

However, I have been struggling to implement the function without declaring the list globally and simply manipulating it within the function. My code is as follows (it works, but I don't like the global declaration of the list).

Relevant snippets of main():

...code to get and check input...
# Convert input to integer cents
    changeowed *= 100

    # Create list of change denominations
    denomlist = [25, 10, 5, 1]

    # Create list of change
    change = make_change(changeowed, denomlist)

    # Count number of elements in change list, return it
    print(len(change))

Recursive function

# Create outlist - this is global
outlist = []

# Recursive function to return a list of coins used
def make_change(amount, denoms):

    # Slice denoms list into first element and rest
    first, *rest = denoms

    # Base case 1 - No change is owed
    if amount <= 0:
        return []

    # Base case 2 - No denominations of money to be used (wont be used in this program)
    if denoms == []:
        return []

    # Recursive case 1 - Current denomination in list is too large to be used to make change
    if (amount < first):
        make_change(amount, rest)

    # Recursive case 2 - Use current denomination to make change
    if (amount >= first):
        outlist.append(first)
        make_change((amount - first), denoms)

    # Resolve call stack
    return outlist

There are a number of problems with the above, including the fact that none of the returns of outlist matters except the last- and so the function is not truly recursive at all since it doesn't use the return value of the previous function call. Ideally I would like to rewrite Recursive case 2 along the following lines

# Recursive case 2 - Use current denomination to make change
if (amount > = first):
return [first, make_change((amount - first, denoms)

With this rewrite, the function would return a list in each case and I would ideally find some way of .extending that list onto some local list variable which would grow with each function call. I have been unable to figure out how to do this.

Is this possible? How does one append or extend the return value of a recursive function onto a locally declared list variable (that is therefore reinitialised with each function call)? Does anybody have any advice on how this function could be rewritten to return a list without declaring that list globally?

2

You could change

    # Recursive case 1 - Current denomination in list is too large to be used to make change
    if (amount < first):
        make_change(amount, rest)

    # Recursive case 2 - Use current denomination to make change
    if (amount >= first):
        outlist.append(first)
        make_change((amount - first), denoms)

to

    # Recursive case 1 - Current denomination in list is too large to be used to make change
    if (amount < first):
        return make_change(amount, rest)

    # Recursive case 2 - Use current denomination to make change
    else:
        return [first] + make_change((amount - first), denoms)

removing any need for an outlist

The second return uses + to concatenate two lists. [first].extend(...) should have the same effect.

| improve this answer | |
  • Thank you very much! This is exactly what I was trying to achieve but had trouble wrapping my head around not having some named list variable to which the return values would be added. Much appreciated, I know my question was rather long and abstract. – dbekker May 4 '19 at 0:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .