# Pset6 - how to recursively .append or .extend a list (cash.py)?

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?

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.

• 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