Baktracking-Funktion, die die Berechnung berechnet, überschreitet die maximale Rekursionstiefe

Ich versuche, eine Funktion zu schreiben, die alle möglichen Kombinationen von Münzen findet, die eine bestimmte Menge liefern, zum Beispiel berechnet sie alle möglichen Wege, um für die Menge 2 britische Pfunde aus der Liste der Konfessionen 1p, 2p, 5p, 10p, 20p, 50p, 1pound, 2pound Ich stecke damit fest und finde die richtige Lösung nicht.

Ich möchte, dass die Hauptfunktion rekursiv ist, weil ich die Rekursion besser verstehen möchte. Der Algorithmus muss zurückverfolgen, wenn die Kombination, die zu einem gewissen Zeitpunkt gefunden wird, den Betrag übersteigt, der abgestimmt werden soll, sollte das Programm zu den vorherigen Schritten zurückkehren und von einem anderen Punkt beginnen.

Bisher habe ich eine normale (nicht rekursive) Funktion geschrieben, die alle möglichen Kombinationen von Münzen in einem bestimmten Land berechnet, wenn jede Münze nur einmal benutzt wird (das ist ziemlich einfach). Ich versuche nicht, die richtige Kombination für eine gegebene Summe zu finden, nur alle möglichen Kombinationen von Münzen.

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 

Jetzt habe ich eine ungeschickte rekursive Funktion, die eine Kombination und einen gewünschten Betrag als Argumente akzeptiert und alle möglichen Möglichkeiten zurückgibt, in denen eine Änderung gleich dieser Menge gegeben werden kann.

 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 

Die Funktion läuft und kommt für sehr kleine Kombinationen korrekt zurück: zB für

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

Es kommt zurück:

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

Aber für größere, wie

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

Sie überschreitet die Rekursionsgrenze. Es läuft bis zu einem gewissen Moment gut, druckt Teilergebnisse aus, aber dann irgendwann übersteigt es maximale Rekursionstiefe.

Was sind die Fehler, die ich mache, welche cuase diese Funktion, um Amok zu laufen? Ist es etwas mit meiner Implementierung von Backtracking? Bin ich einen Fall auslassen? Wie kann man diese Funktion so optimieren, dass sie die maximale Rekursionstiefe nicht überschreitet?

Danke im Voraus!

EDIT: Hier ist die Rückverfolgung:

  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 

Und das letzte Teilergebnis, kurz vor dem Bruch der Funktion (mit test3 genannt)

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

  • Kreuz Produkt von Sets mit Rekursion
  • Maximales Niveau der Rekursion in Python
  • Berechnungsdeterminante einer Matrix (nxn) rekursiv
  • Trennungsliste mit Rekursion
  • Rekursive Funktion gibt keine in Python zurück [doppelte]
  • Refactoring zur Beseitigung der globalen Variablen in rekursiver Funktion
  • Python rekursiver Funktionsfehler: "maximale Rekursionstiefe überschritten"
  • Python - Eigenschaftseinstellung aus der Liste verursacht maximale Rekursionstiefe überschritten
  • One Solution collect form web for “Baktracking-Funktion, die die Berechnung berechnet, überschreitet die maximale Rekursionstiefe”

    Zunächst einmal, wie die erste Antwort auf diese Frage zeigt, ist wegen der Semantik von Python als Sprache die Rekursion kein besonders effizientes Paradigma. Allerdings ist es, wie bereits erwähnt, möglich, sys.setrecursionlimit(2000) . (Oder so viel du brauchst) Ich möchte betonen, dass dies die "faulen" Lösung ist, empfehle ich dringend, deine erste (nicht rekursive) Version zu verwenden.

    Python ist die beste Programmiersprache der Welt.