Recursion in Python 3.2

Question

I am trying to wrap my head around recursion and have posted a working algorithm to produce all the subsets of a given list.

def genSubsets(L):
    res = []
    if len(L) == 0:
        return [[]]
    smaller = genSubsets(L[:-1])
    extra = L[-1:]
    new = []
    for i in smaller:
        new.append(i+extra)
    return smaller + new

Let's say my list is L = [0,1], correct output is [[],[0],[1],[0,1]]

Using print statements I have narrowed down that genSubsets is called twice before I ever get to the for loop. That much I get.

But why does the first for loop initiate a value of L as just [0] and the second for loop use [0,1]? How exactly do the recursive calls work that incorporate the for loop?

Answer 1

I think this would actually be easier to visualize with a longer source list. If you use [0, 1, 2], you'll see that the recursive calls repeatedly cut off the last item from the list. That is, recusion builds up a stack of recursive calls like this:

genSubsets([0,1,2])
    genSubsets([0,1])
        genSubsets([0])
            genSubsets([])

At this point it hits the "base case" of the recursive algorithm. For this function, the base case is when the list given as a parameter is empty. Hitting the base case means it returns an list containing an empty list [[]]. Here's how the stack looks when it returns:

genSubsets([0,1,2])
    genSubsets([0,1])
        genSubsets([0]) <- gets [[]] returned to it

So that return value gets back to the previous level, where it is saved in the smaller variable. The variable extra gets assigned to be a slice including only the last item of the list, which in this case is the whole contents, [0].

Now, the loop iterates over the values in smaller, and adds their concatenation with extra to new. Since there's just one value in smaller (the empty list), new ends up with just one value too, []+[0] which is [0]. I assume this is the value you're printing out at some point.

Then the last statement returns the concatenation of smaller and new, so the return value is [[],[0]]. Another view of the stack:

genSubsets([0,1,2])
    genSubsets([0,1]) <- gets [[],[0]] returned to it

The return value gets assigned to smaller again, extra is [1], and the loop happens again. This time, new gets two values, [1] and [0,1]. They get concatenated onto the end of smaller again, and the return value is [[],[0],[1],[0,1]]. The last stack view:

genSubsets([0,1,2]) <- gets [[],[0],[1],[0,1]] returned to it

The same thing happens again, this time adding 2s onto the end of each of the items found so far. new ends up as [[2],[0,2],[1,2],[0,1,2]].

The final return value is [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]