I'm trying to write a function that finds all possible combinations of coins that yield a specified amount, for example it calculates all possible way to give change for the amount 2 British pounds from the list of denominations 1p, 2p, 5p,10p,20p,50p,1pound,2pound. I'm stuck with this and can't find the right solution.

I want the main function to be recursive, because I want to understand recursion better. The algorithm must backtrack, if the combination found at some moment exceeds the amount which is to be matched the program should return to previous steps and start from different point.

Thus far I've written a normal (not recursive) function that computes all possible combinations of coins in a given country if each coin is used only once (this is fairly straightforward). I am not trying to find the right combination for a given sum yet, just all possible combinations of coins.

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 += 1return combs

Now I have a clumsy recursive function that accepts a combination and desired amount as arguments and returns all possible ways in which a change equal to this amount can be given.

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 exitreturn rightOnesrightOnes.append(comb_)elif sum(comb.elements()) > goal:#this is meant to be backtrackingreturn Falsefor k in comb:comb[k] += 1if findSum(comb,goal,rightOnes) != False:return findSum(comb,goal,rightOnes)else:comb[k] = 1return rightOnes

The function runs and returns correctly for very small combinations: e.g. for

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

It returns:

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

But for larger ones, such as

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

it exceeds the limit of recursion. It runs fine until some moment, prints out partial results but then at some point it exceeds maximum recursion depth.

What are the mistakes I'm making which cuase this function to run amok? Is it something with my implementation of backtracking? Am I omitting some case? How to optimize this function so that it does not exceed maxim recursion depth?

Thanks in advance!

EDIT: Here is the traceback:

   if findSum(comb,goal,rightOnes) != False:File "C:\playground\python\problem31.py", line 105, in findSumif sum(comb.elements()) == goal:File "C:\Python27\lib\collections.py", line 459, in elementsreturn _chain.from_iterable(_starmap(_repeat, self.iteritems()))RuntimeError: maximum recursion depth exceeded while calling a Python object

and the last partial result, just before the break of the function (called with 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})]

First of all, as the first answer to this question shows, because of the semantics of Python as a language, recursion isn't a particularly efficient paradigm. However, as is pointed out there, it is possible to use sys.setrecursionlimit(2000). (Or however much you need) I want to stress that this is the "lazy" solution, I strongly recommend using your first (non-recursive) version instead.