# Recursive Function to Produce Constrained List of Integer Partitions

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

• 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. – Reinderien Jul 1 '20 at 18:31
• 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. – AJNeufeld Jul 3 '20 at 18:41

## 1 Answer

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

In : import sys

In : sys.getrecursionlimit()
Out: 1000


So we can easily design a test that will fail

In : 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 : sys.setrecursionlimit(1500)

In : partition(1000, {1})
Out:
{(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