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))
# 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?