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

Примеры:

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

мы можем сделать 78 из 3х25 + 3x1, так что требуется 6 монет

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

48 = 2x24так что достаточно 2 монеты

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

мы можем сделать 35 из 2х16 + 1x3так что достаточно 3 монеты

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

def C(i, coins, cdict = None):
    if cdict == None:
        cdict = {}
    if i