1
\$\begingroup\$

I have modified a recursive function designed to print all the integer partitions of a positive integer to create a function that returns all partitions of the "number" parameter if they include a number contained in the "interesting" parameter. I would like to use this for very large numbers (10-50 million), but am getting errors referring to the recursion depth. My question is whether there is a way to do this more efficiently by recursion, and if not, whether there is another way to do this.

def partition(number, interesting): # returns all the partitions of number that are included in the interesting list
    answer = set()
    if number in interesting:
        answer.add((number, ))
    
    for x in range(1, number):
        if x in interesting: 
            for y in partition(number - x, interesting):
                answer.add(tuple(sorted((x, ) + y)))
    return answer
\$\endgroup\$
  • \$\begingroup\$ If you have more of the program you haven't posted, please include it. Also, please rename the question to reflect what you're doing with the application, not your review concerns. \$\endgroup\$ – Reinderien Jul 1 at 18:31
  • \$\begingroup\$ What do you do with your answer? You are returning a Set[Tuple[int,...]], but do you need to return the entire set at once, or could you use return the set elements one at a time using a generator? Is this a programming challenge? If so post a link to the problem, as well as the full problem description in the question, including limits, such as the number of interesting numbers, as well as their ranges. \$\endgroup\$ – AJNeufeld Jul 3 at 18:41
0
\$\begingroup\$

Python is not designed for recursion. To avoid stack overflows there is a limit

In [2]: import sys

In [3]: sys.getrecursionlimit()
Out[3]: 1000

So we can easily design a test that will fail

In [4]: partition(1000, {1})
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-4-884568e60acd> in <module>()
----> 1 partition(1000, {1})

<ipython-input-1-60a0eb582d3c> in partition(number, interesting)
      6     for x in range(1, number):
      7         if x in interesting:
----> 8             for y in partition(number - x, interesting):
      9                 answer.add(tuple(sorted((x, ) + y)))
     10     return answer

... last 1 frames repeated, from the frame below ...

<ipython-input-1-60a0eb582d3c> in partition(number, interesting)
      6     for x in range(1, number):
      7         if x in interesting:
----> 8             for y in partition(number - x, interesting):
      9                 answer.add(tuple(sorted((x, ) + y)))
     10     return answer

RecursionError: maximum recursion depth exceeded in comparison

You may increase the recursion limit

In [5]: sys.setrecursionlimit(1500)

In [6]: partition(1000, {1})
Out[6]: 
{(1, ...

but that is only applicable if your numbers are guaranteed to be in a certain range. Most probably you should implement a non-recursive solution. For 10-50 million you have to.

If your problem e. g. guarantees 1 <= number <= 500 you should still do some assertions in your function

assert 1 <= number <= 500
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.