Dado un monto objetivo y una lista de denominaciones de monedas, se supone que mi código debe encontrar el menor número de monedas necesarias para alcanzar el monto objetivo.

Ejemplos:

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

Podemos hacer 78 desde 3x.25 + 3x1, por lo que se requieren 6 monedas

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

48 = 2x24, entonces 2 monedas son suficientes

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

Podemos hacer 35 desde 2x.dieciséis + 1x3, entonces bastan 3 monedas

Hice el código con para bucles, pero ¿cómo lo hago 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]