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

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.

  • Gibt es eine Möglichkeit, eine rekursive Funktion zu schreiben, die alle ganzen Zahlen in einer Liste durchsucht und sieht, ob irgendwelche zwei gleich einer negativen Summe sind?
  • Ich versuche, eine Funktion zu machen, die max aus verschachtelter Liste zurückgibt?
  • Python Recursive Funktion fehlende Ergebnisse
  • Python Recursive Funktion für Collatz Conjecture
  • Warum gibt meine rekursive Funktion keine?
  • Python: Rekursive Funktion, um die größte Zahl in der Liste zu finden
  • Rekursionsfunktion funktioniert nicht richtig
  • Finde alle Index mit Rekursion
  • Python-Funktion kehrt nach Rekursion nicht zurück
  • Maximales Niveau der Rekursion in Python
  • Rekursiv finden Sie die kth größte int in Liste der Liste der int in Python
  • Python ist die beste Programmiersprache der Welt.