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.

Improve this question
4
  • Related stackoverflow.com/questions/3323001/… Commented Apr 26, 2018 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. Commented Apr 26, 2018 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. Commented Apr 26, 2018 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. Commented Apr 26, 2018 at 20:02

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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

Improve this answer

1 Comment

Arg, yes I know how to do the DP solution. Just being new to python I was looking how to optimize the code above.
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.

Improve this answer

6 Comments

I like this answer. But I still think it needs to be c + 1 <= 0: because c is len(coins) -1 not len(coins)..
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.
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?
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
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.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.