Dado um valor-alvo e uma lista de denominações de moeda, meu código deve encontrar o menor número de moedas necessárias para atingir o valor-alvo.

Exemplos:

C(78, [1, 5, 10, 25, 50]) = 6

nós podemos fazer 78 de 3x25 + 3x1então 6 moedas são necessárias

C(48, [1, 7, 24, 42]) = 2

48 = 2x24, então 2 moedas são suficientes

C(35, [1, 3, 16, 30, 50]) = 3

nós podemos fazer 35 de 2x16 + 1x3, então 3 moedas são suficientes

Eu fiz o código com loops for, mas como faço isso recursivo?

def C(i, coins, cdict = None):
    if cdict == None:
        cdict = {}
    if i <= 0:
        cdict[i] = 0
        return cdict[i]
    elif i in cdict:
        return cdict[i]
    elif i in coins:
        cdict[i] = 1
        return cdict[i]
    else:
        min = 0
        for cj in coins:
            result = C(i - cj, coins)
            if result != 0:
                if min == 0 or (result + 1) < min:
                    min = 1 + result
        cdict[i] = min
        return cdict[i]