Recursive Function to Produce Constrained List of Integer Partitions

Question

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

• Reinderien: 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.
• AJNeufeld: 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.

Answer 1

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