Функция Baktracking, которая рассчитывает изменение, превышает максимальную глубину рекурсии

Question

Я пытаюсь написать функцию, которая находит все возможные комбинации монет, которые дают определенную сумму, например, она рассчитывает все возможные способы, чтобы дать изменение на сумму 2 британских фунта из списка достоинств 1p, 2p, 5p,10p,20p,50p,1pound,2pound. Я застрял с этим и не могу найти правильное решение.

Я хочу, чтобы основная функция была рекурсивной, потому что я хочу лучше понять рекурсию. Алгоритм должен возвращаться назад, если найденная комбинация в какой-то момент превышает сумму, которую необходимо сопоставить, программа должна вернуться к предыдущим шагам и начать с другой точки.

До сих пор я написал обычную (не рекурсивную) функцию, которая вычисляет все возможные комбинации монет в данной стране, если каждая монета используется только один раз (это довольно просто). Я пока не пытаюсь найти правильную комбинацию для данной суммы, просто все возможные комбинации монет.

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

Теперь у меня есть неуклюжая рекурсивная функция, которая принимает комбинацию и желаемую сумму в качестве аргументов и возвращает все возможные способы, которыми может быть дано изменение, равное этой сумме.

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

Функция запускается и возвращается правильно для очень маленьких комбинаций: например, для

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

Возвращает:

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

Но для более крупных, таких как

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

это превышает предел рекурсии. Он работает нормально до некоторого момента, выводит частичные результаты, но затем в какой-то момент он превышает максимальную глубину рекурсии.

Какие ошибки я делаю, потому что эта функция работает безумно? Это что-то с моей реализацией возврата? Я опускаю какой-то случай? Как оптимизировать эту функцию, чтобы она не превышала максимальную глубину рекурсии?

Заранее спасибо!

РЕДАКТИРОВАТЬ: Вот трассировка:

   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

и последний частичный результат, непосредственно перед прерыванием функции (вызывается с 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

Прежде всего, как показывает первый ответ на этот вопрос, из-за семантики Python как языка рекурсия не является особенно эффективной парадигмой. Однако, как указано там, можно использовать sys.setrecursionlimit(2000), (Или сколько вам нужно) Я хочу подчеркнуть, что это "ленивое" решение, я настоятельно рекомендую вместо этого использовать вашу первую (нерекурсивную) версию.