Funkcja Baktracking, która oblicza zmianę przekracza maksymalną głębokość rekurencji

Question

Próbuję napisać funkcję, która znajdzie wszystkie możliwe kombinacje monet, które dają określoną ilość, na przykład oblicza wszystkie możliwe sposoby podania zmiany za kwotę 2 funtów brytyjskich od lista denominacji 1p, 2p, 5p, 10p, 20p, 50p, 1pound, 2pound. Utknąłem z tym i nie mogę znaleźć odpowiedniego rozwiązania.

Chcę, aby główna funkcja była rekursywna, ponieważ chcę lepiej zrozumieć rekursję. Algorytm musi się wycofać, jeśli kombinacja znaleziona w pewnym momencie przekroczy ilość, która ma zostać dopasowana, program powinien powrócić do poprzednich kroków i zacząć od innego punktu.

Do tej pory napisałem normalną (nierekursywną) funkcję, która oblicza wszystkie możliwe kombinacje monet w danym kraju, jeśli każda moneta jest używana tylko raz (jest to dość proste). Nie próbuję znaleźć odpowiedniej kombinacji dla danej sumy, tylko wszystkie możliwe kombinacje monet.

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 

Teraz ma niezgrabny funkcji rekurencyjnej, który akceptuje połączenie i pożądanej ilości jako argumenty i zwraca wszystkich możliwych sposobów, w których zmiana równa ilość ta może być podana.

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 

Funkcja działa i zwraca poprawnie dla bardzo małych kombinacji: np. dla

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

Zwraca:

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

Ale dla dużych przedsiębiorstw, takich jak

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

przekroczy limit rekursji. Działa do pewnego momentu, drukuje częściowe wyniki, ale w pewnym momencie przekracza maksymalną głębokość rekursji.

Jakie błędy popełniam, aby uruchomić tę funkcję w amoku? Czy jest to coś z moją implementacją backtrackingu? Czy pomijam jakąś sprawę? Jak zoptymalizować tę funkcję, aby nie przekroczyła maksymalnej głębokości rekurencji?

Z góry dziękuję!

EDIT: Oto 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 

a ostatni wynik częściowy, tuż przed przerwą funkcji (nazywanej z 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

Przede wszystkim, jak Pierwsza odpowiedź na this question pokazuje, ze względu na semantykę Pythona jako języka, rekurencja nie jest szczególnie wydajnym paradygmatem. Jednakże, jak wskazano tam, możliwe jest użycie sys.setrecursionlimit(2000). (Lub jakkolwiek potrzebujesz) Chcę podkreślić, że jest to "leniwe" rozwiązanie, zdecydowanie zalecam używanie swojej pierwszej (nierekurencyjnej) wersji.