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 &quot;number&quot; parameter if they include a number contained in the &quot;interesting&quot; 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
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)
&lt;ipython-input-4-884568e60acd&gt; in &lt;module&gt;()
----&gt; 1 partition(1000, {1})

&lt;ipython-input-1-60a0eb582d3c&gt; in partition(number, interesting)
      6     for x in range(1, number):
      7         if x in interesting:
----&gt; 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 ...

&lt;ipython-input-1-60a0eb582d3c&gt; in partition(number, interesting)
      6     for x in range(1, number):
      7         if x in interesting:
----&gt; 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 &lt;= number &lt;= 500 you should still do some assertions in your function
assert 1 &lt;= number &lt;= 500