La función Baktracking que calcula el cambio excede la profundidad máxima de recursión

Estoy tratando de escribir una función que encuentre todas las combinaciones posibles de monedas que produzcan una cantidad específica, por ejemplo, calcula todas las formas posibles de cambiar la cantidad de 2 libras esterlinas británicas de la lista de denominaciones 1p, 2p, 5p, 10p, 20p, 50p, 1pound, 2pound. Estoy atascado con esto y no puedo encontrar la solución correcta.

Quiero que la función principal sea recursiva, porque quiero entender mejor la recursión. El algoritmo debe retroceder, si la combinación encontrada en algún momento excede la cantidad que debe coincidir, el progtwig debe regresar a los pasos anteriores y comenzar desde un punto diferente.

Hasta ahora he escrito una función normal (no recursiva) que calcula todas las combinaciones posibles de monedas en un país determinado si cada moneda se usa solo una vez (esto es bastante sencillo). No estoy tratando de encontrar la combinación correcta para una sum dada, solo todas las combinaciones posibles de monedas.

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 

Ahora tengo una función recursiva torpe que acepta una combinación y una cantidad deseada como argumentos y devuelve todas las formas posibles en que se puede dar un cambio igual a esta cantidad.

 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 

La función se ejecuta y devuelve correctamente para combinaciones muy pequeñas: por ejemplo, para

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

    Vuelve:

      [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})] 

    Pero para los más grandes, como

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

    supera el límite de recursión. Funciona bien hasta cierto momento, imprime resultados parciales pero en algún momento supera la profundidad máxima de recursión.

    ¿Cuáles son los errores que estoy cometiendo en relación con esta función para ejecutarse de forma desordenada? ¿Es algo con mi implementación de backtracking? ¿Estoy omitiendo algún caso? ¿Cómo optimizar esta función para que no exceda la profundidad máxima de recursión?

    ¡Gracias por adelantado!

    EDITAR: Aquí está el rastreo:

      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 

    y el último resultado parcial, justo antes de la interrupción de la función (llamado 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})] 

    En primer lugar, como muestra la primera respuesta a esta pregunta , debido a la semántica de Python como lenguaje, la recursión no es un paradigma particularmente eficiente. Sin embargo, como se señala allí, es posible utilizar sys.setrecursionlimit(2000) . (O por mucho que necesites) Quiero enfatizar que esta es la solución “perezosa”, te recomiendo usar tu primera versión (no recursiva) en su lugar.