Getting all recursion results in a list

Question

I'm learning about python recursion. To practice i'm giving a task to find all subset of a list. For example the function:

subset([1,2)] should return [[1,2],[1],[2],[]]

I can get my function print these results with the help of recursion

def subset(List):
   print(List)
   n = len(List)
   if n > 2:
      for i in range(n):
         subset(List[:i]+List[i+1:])

   if n == 2:
      subset([List[0]])
      subset([List[1]])
   if n == 1:
      subset([])
pass

L = [1,2]
test = subset(L)

The print statement prints:

[1, 2], [1], [], [2], []

I would love to have the function to not print but instead return this in a list as given by the desired result.

I Would love your take on this.

Answer 1

First off, if you do not actually have to implement it yourself, the standard library is happy to help.

But this is an interesting problem for studying recursion, so let's take a closer look.

Similarly to here, for complex uses of recursion that a) make multiple recursive calls at a time and b) need to "accumulate" the results in some way, my recommendation is to write a recursive generator. You can convert it mechanically:

• replace print with yield

• yield from the recursive calls (as I noted on the other answer there, for cases where you don't need to accumulate results, you would generally want to return these).

Then from outside the recursion, you can collect the results into a list, or iterate over them directly.

However, there is also an issue with your algorithm: results that are missing two or more of the original elements will appear more than once (as you can already see), because there is more than one recursive "path" to them. The algorithm you want instead is:

• Recursively get subsets that don't include the first element
• For each of those, emit two results: one with the first element prepended, and one without

So instead of yield from we will iterate over the results, do some modification, and yield inside that loop.

Putting all that together, it looks like:

def power_set(items):
    if not items: # empty set; base case for recursion.
        yield items
        return
    # Pull off the first element,
    first, *rest = items
    # then iterate over the recursive results on the rest of the elements.
    for without_first in power_set(rest):
        yield [first] + without_first
        yield without_first

# let's test it:
list(power_set([1,2,3]))
# [[1, 2, 3], [2, 3], [1, 3], [3], [1, 2], [2], [1], []]
# Good, just what we want - with no duplicates.