Biorąc pod uwagę kwotę docelową i listę nominałów monet, mój kod ma znaleźć najmniej monet potrzebnych do osiągnięcia kwoty docelowej.

Przykłady:

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

możemy zrobić 78 z 3x25 + 3x1, więc wymagane jest 6 monet

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

48 = 2x24, więc 2 monety są wystarczające

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

możemy zrobić 35 z 2x16 + 1x3, więc wystarczą 3 monety

Zrobiłem kod z pętlami for, ale jak zrobić to rekurencyjnie?

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]