2

So I have a recursive solution to the make change problem that works sometimes. It is:

def change(n, c):
   if (n == 0):
      return 1

   if (n < 0):
      return 0;

   if (c + 1 <= 0 and n >= 1):
      return 0

   return change(n, c - 1) + change(n - coins[c - 1], c);

where coins is my array of coins. For example [1,5,10,25]. n is the amount of coins, for example 1000, and c is the length of the coins array - 1. This solution works in some situations. But when I need it to run in under two seconds and I use:

coins: [1,5,10,25]
n: 1000

I get a:

RecursionError: maximum recursion depth exceeded in comparison

So my question is, what would be the best way to optimize this. Using some sort of flow control? I don't want to do something like.

# Set recursion limit
sys.setrecursionlimit(10000000000)

UPDATE:

I now have something like

def coinss(n, c):

   if n == 0:
      return 1

   if n < 0:
      return 0

   nCombos = 0
   for c in range(c, -1, -1):
      nCombos += coinss(n - coins[c - 1], c)


   return nCombos

but it takes forever. it'd be ideal to have this run under a second.

David Dennis
  • 702
  • 2
  • 9
  • 26
  • Related https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it – Hackerman Apr 26 '18 at 19:56
  • Gnerally, you should take this as a sign that you are taking a recursive approach to a non-recursive problem. Your problem looks like a textbook example for a dynamic programming solution. – Patrick Haugh Apr 26 '18 at 19:58
  • @PatrickHaugh you're not wrong. I do have DP solution. Just trying to lean some things. I.E if the above solution can be optimized to run "faster" using recursion. – David Dennis Apr 26 '18 at 20:00
  • Usually not. The advantages to recursion are the simple, clean code it can produce and the fact that man problems are recursive, so have natural recursive solutions. Especially in languages like Python, that don't optimize recursive algorithms, recursion can be pretty expensive. – Patrick Haugh Apr 26 '18 at 20:02

3 Answers3

1

As suggested in the answers above you could use DP for a more optimal solution. Also your conditional check - if (c + 1 <= 0 and n >= 1)

should be

if (c <= 1 ):

as n will always be >=1 and c <= 1 will prevent any calculations if the number of coins is lesser than or equal to 1.

Debjani
  • 31
  • 6
0

While using recursion you will always run into this. If you set the recursion limit higher, you may be able to use your algorithm on a bigger number, but you will always be limited. The recursion limit is there to keep you from getting a stack overflow.

The best way to solved for bigger change amounts would be to swap to an iterative approach. There are algorithms out there, wikipedia: https://en.wikipedia.org/wiki/Change-making_problem

segfault116
  • 1
0

Note that you have a bug here:

if (c + 1 <= 0 and n >= 1):

is like

if (c <= -1 and n >= 1):

So c can be 0 and pass to the next step where you pass c-1 to the index, which works because python doesn't mind negative indexes but still false (coins[-1] yields 25), so your solution sometimes prints 1 combination too much.

I've rewritten your algorithm with recursive and stack approaches:

Recursive (fixed, no need for c at init thanks to an internal recursive method, but still overflows the stack):

coins = [1,5,10,25]

def change(n):
    def change_recurse(n, c):
       if n == 0:
          return 1

       if n < 0:
          return 0;

       if c <= 0:
          return 0

       return change_recurse(n, c - 1) + change_recurse(n - coins[c - 1], c)
    return change_recurse(n,len(coins))

iterative/stack approach (not dynamic programming), doesn't recurse, just uses a "stack" to store the computations to perform:

def change2(n):
    def change_iter(stack):
        result = 0
        # continue while the stack isn't empty
        while stack:
            # process one computation
            n,c = stack.pop()
            if n == 0:
              # one solution found, increase counter
              result += 1

            if n > 0 and c > 0:
                # not found, request 2 more computations
                stack.append((n, c - 1))
                stack.append((n - coins[c - 1], c))

        return result
    return change_iter([(n,len(coins))])

Both methods return the same values for low values of n.

for i in range(1,200):
    a,b = change(i),change2(i)
    if a != b:
        print("error",i,a,b)

the code above runs without any error prints.

Now print(change2(1000)) takes a few seconds but prints 142511 without blowing the stack.

Jean-François Fabre
  • 137,073
  • 23
  • 153
  • 219
  • I like this answer. But I still think it needs to be c + 1 <= 0: because c is len(coins) -1 not len(coins).. – David Dennis Apr 26 '18 at 20:31
  • you never said that starting `c` was `len(coins)-1`, so I used `len(coins)`. If `c + 1 == 1` then `c` can be 0 and `coins[c - 1]` is wrong: it takes the last item (25) instead of the previous item. – Jean-François Fabre Apr 26 '18 at 20:32
  • hmm I said " c is the length of the coins array - 1" .. So my solution is wrong then? So that might be causing the overflow? – David Dennis Apr 26 '18 at 20:34
  • okay, but there's still an issue with your program. And you don't need to know the length of the coins array. You can get rid of that parameter by using `len(coins)` internally. Check with only coins 1 & 5 with your solution and try to enter 5: you'll get 3 whereas the actual solution is 2. but that's not causing the overflow. Too many recursive calls cause the overflow – Jean-François Fabre Apr 26 '18 at 20:35
  • Yes, hence the question. I'm trying to find a recursive solution that does not overflow the stack. Playing with recursive calls in a for loop right now. – David Dennis Apr 26 '18 at 20:50
  • I wonder if there is a way to use recursion while you save the immediate results. – David Dennis Apr 26 '18 at 23:04