0

I'm a novice in CS and I just tried to use recursion solve a change-making problem, which is mentioned in another question Recursive change-making algorithm

def change(total, coins):
    def coin_change(remain, position, changes=None):
        changes=[] if changes is None else changes
        if remain == 0:
            return len(changes), changes
        elif remain < 0 or position == -1:
            return float('inf'), changes
        else:
            strategy1 = coin_change(remain, position-1, changes)
            strategy2 = coin_change(remain-coins[position], position, 
                                    changes+[coins[position]])
        if strategy1[0] >= strategy2[0]:
            return strategy2
        else:
            return strategy1
    return coin_change(total, len(coins)-1, changes=None)

the code works well when given small inputs such as (49, [1,5,12,24]), but when the input gets larger, the code becomes very slow and when given the likely of (1000, [1,5,12,24]), errors pop up, just like this:

File "********\coin_change.py", line 56, in testperformance
function1(1480, [1, 7, 24, 42])

Though I have solved this problem by utilizing some dynamic programming techniques, I'm really curious about what's wrong with my initial codes. Is it a stack overflow problem? How does it happen? Hope some an explicit explication or reference materials.

Cœur
  • 37,241
  • 25
  • 195
  • 267
xwb1989
  • 233
  • 1
  • 14
  • 1
    What is the actual error? You've given us just the location of an unspecified error. But yes, it appears you are exceeding the maximum recursion depth of 1000. – chepner Sep 22 '12 at 15:29
  • The actual error information was an infinite loop of what I have posted, no other information showed up. So did you mean that recursion has a depth limit of 1000? – xwb1989 Sep 22 '12 at 16:28
  • The Python interpreter, in order to avoid infinite recursion, will stop any recursion (even if it really would have completed) after 1000 recursive calls. – chepner Sep 22 '12 at 16:31

0 Answers0