I am trying my way around practising recursion and I want to find the minimum ways to generate a sum with given coins.

I did figure out a way to do using a global variable but I've heard it's not really optimal to do it this way

This is my code

minres = 10000
def count(sum, i, coins, temp, res):
    global minres
    if sum == 0:
        minres = min(minres, res)
        return

    if sum < 0:
        return

    if i == len(coins):
        return

    temp.append(coins[i])
    count(sum-coins[i], i, coins, temp, res 1)
    temp.pop()
    count(sum, i 1, coins, temp, res)

    return minres


coins = [9, 6, 5, 1]
print(count(11, 0, coins, [], 0))

This code works and I get the answer 2, but is there a way I can do it without a global variable or something of the sort?

CodePudding user response：

Here's a modified version of your function that doesn't rely on a global definition of minres. By passing minres to and returning it from every function call, it no longer needs to be "remembered" outside the scope of each function call:

def count(sm, i, coins, res, temp=None, minres = 10000):
    if temp is None:
        temp = []
    if sm == 0:
        minres = min(minres, res)

    if sm < 0:
        return minres

    if i == len(coins):
        return minres

    temp.append(coins[i])
    minres = count(sm-coins[i], i, coins, res 1, temp, minres)
    temp.pop()
    minres = count(sm, i 1, coins, res, temp, minres)

    return minres

A couple of other changes I've made:

1. temp = [] in your call signature is dicey because the default argument is mutable. Better to use None as a cue within your call to default temp to [].
2. I've avoided using sum as a variable name given it is a builtin function within Python. By reassigning something to the name sum other than its original meaning, you risk confusing things later on.