Учитывая целевое количество и список номиналов монет, мой код должен найти наименьшее количество монет, необходимых для достижения целевого количества.

Примеры:

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

we can make 78 from 3x25 + 3x1, so 6 coins are required

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

48 = 2x24, so 2 coins are sufficient

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

we can make 35 from 2x16 + 1x3, so 3 coins suffice

Я сделал код с циклами for, но как мне сделать его рекурсивным?

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]