CODEWITHSUNDEEP
pythonlistrecursionpython-3.x
Richie Cunningham
Richie Cunningham

Reputation: 31

Recursion in Python 3.2

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?

Upvotes: 3

Views: 691

Answers (2)

phant0m
phant0m

Reputation: 16905

I am no big fan of trying to visualize the entire call graph for recursive function to understand what they do.

I believe there is a much simpler way:

Enter fairy tale land where recursive functions do the right thing™.

Just assume that genSubsets(L) works:

# This computes the powerset of the list L minus the last element
smaller = genSubsets(L[:-1])

Because this magically worked, the only entries that are missing are those, that contain the last element.

This fragment constructs all those missing subsets:

new = []
for i in smaller:
    new.append(i+extra)

Now we have those subsets containing the last element in new and we have those subsets not containing the last element in smaller.

It follows that we must now have all subsets, so we can return new + smaller.

The only thing left is the base case to make sure the recursion stops. Because the empty set (or list in this case) is an element of every power set, we can use that to stop the recursion: Requesting the powerset of an empty set is a set containing the empty set. So our base case is correct. Since every recursive step removes one element off the list, the base case must be encountered at some time.

Thus, the code really does produce the power set.

Note: The principle behind this is that of induction. If something works for some known n0, and we can prove that: The algorithm working for n implies it works for n+1, it must thus work for all n ≥ n0.

Upvotes: 3

Blckknght
Blckknght

Reputation: 104762

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]]

Upvotes: 7

Related Questions