La funzione di Baktracking che calcola la modifica supera la profondità massima di ricorsione

Question

Sto provando a scrivere una funzione che trova tutte le combinazioni possibili di monete che producono una quantità specificata, ad esempio calcola tutto il possibile modo di dare un cambio per la somma di 2 sterline inglesi l'elenco delle denominazioni 1p, 2p, 5p, 10p, 20p, 50p, 1pound, 2pound. Sono bloccato con questo e non riesco a trovare la soluzione giusta.

Voglio che la funzione principale sia ricorsiva, perché voglio capire meglio la ricorsione. L'algoritmo deve tornare indietro, se la combinazione trovata in un momento supera l'importo che deve essere abbinato, il programma dovrebbe tornare ai passaggi precedenti e partire da un punto diverso.

Finora ho scritto una funzione normale (non ricorsiva) che calcola tutte le combinazioni possibili di monete in un dato paese se ogni moneta viene utilizzata una sola volta (questo è abbastanza semplice). Non sto ancora cercando la combinazione giusta per una data somma, solo tutte le possibili combinazioni di monete.

def calcCoins(coins): 
    """ 
    returns all possible combinations of coins, when called with 
    [1,2,5,10,20,50,100,200] returns a list of 126 Counters containing 
    for instance Counter{1:1}, Counter{1:1,2:1,5:1}, Counter {50:1,100:1} etc 
    """ 
    i,combs = 1, [] 
    while i < len(coins): 
     for x in combinations(coins,i): 
      combs.append(Counter(x)) 
     i += 1 
    return combs 

Ora ho una funzione ricorsiva goffo che accetta una combinazione e la quantità desiderata come argomenti e restituisce tutti i possibili modi in cui può essere dato un cambio pari a tale importo.

def findSum(comb,goal,rightOnes): 
    if rightOnes == None: 
     rightOnes = [] 
    if sum(comb.elements()) == goal: 
     comb_ = Counter(comb) 
     if comb_ in rightOnes: 
      # probably a cycle, return combinations gathered and exit 
      return rightOnes 
     rightOnes.append(comb_) 
    elif sum(comb.elements()) > goal: 
     #this is meant to be backtracking 
     return False 
    for k in comb: 
     comb[k] += 1 
     if findSum(comb,goal,rightOnes) != False: 
      return findSum(comb,goal,rightOnes) 
     else: 
      comb[k] = 1 
    return rightOnes 

Le piste di funzione e restituisce in modo corretto per molto piccole combinazioni: per esempio per

test2 = Counter({10: 1, 20: 1}) 
findSum(test2,200,[]) 

Restituisce:

[Counter({10: 18, 20: 1}), Counter({10: 16, 20: 2}), 
    Counter({10: 14, 20: 3}), Counter({10: 12, 20: 4}), 
    Counter({10: 10, 20: 5}), Counter({10: 8, 20: 6}), 
    Counter({20: 7, 10: 6}), Counter({20: 8, 10: 4}), 
    Counter({20: 9, 10: 2})] 

Ma per quelli più grandi, come ad esempio

test3 = Counter({1: 1, 2: 1, 10: 1}) 
test4 = Counter({1: 1, 2: 1, 100: 1, 10: 1}) 

si supera il limite di ricorsione. Funziona bene fino a un certo momento, stampa risultati parziali ma poi ad un certo punto supera la massima profondità di ricorsione.

Quali sono gli errori che sto facendo e perché questa funzione si esegue in modo incontrollato? È qualcosa con la mia implementazione del backtracking? Sto omettendo un caso? Come ottimizzare questa funzione in modo che non superi la massima profondità di ricorsione?

Grazie in anticipo!

EDIT: Ecco traceback:

if findSum(comb,goal,rightOnes) != False: 
    File "C:\playground\python\problem31.py", line 105, in findSum 
    if sum(comb.elements()) == goal: 
    File "C:\Python27\lib\collections.py", line 459, in elements 
    return _chain.from_iterable(_starmap(_repeat, self.iteritems())) 
    RuntimeError: maximum recursion depth exceeded while calling a Python object 

e l'ultimo risultato parziale, poco prima della pausa della funzione (chiamata con test3)

[Counter({1: 163, 2: 1, 20: 1, 10: 1, 5: 1}), Counter({1: 161, 2: 2, 20: 1, 10: 1, 5: 1}), 
Counter({1: 159, 2: 3, 20: 1, 10: 1, 5: 1}), Counter({1: 157, 2: 4, 20: 1, 10: 1, 5: 1}), 
Counter({1: 155, 2: 5, 20: 1, 10: 1, 5: 1}), Counter({1: 153, 2: 6, 20: 1, 10: 1, 5: 1})] 

Answer 1

Innanzitutto, come la prima risposta a this question mostra, a causa della semantica di Python come linguaggio, la ricorsione non è un paradigma particolarmente efficiente. Tuttavia, come indicato in precedenza, è possibile utilizzare sys.setrecursionlimit(2000). (O per quanto tu ne abbia bisogno) Voglio sottolineare che questa è la soluzione "pigra", ti consiglio caldamente di usare la tua prima versione (non ricorsiva).