[Tutor] recursion and power sets

[alice]

Ouch! I think I've injured my brain on this one.
I'm beginning to think recursion is not so cool after all.....

I was trying to write a function that would take a set - represented as a list 
with non repeating elements - and return the power set, so given:

[1,2,3]

it should return:

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

After much general confusion, this is what I eventually came up with:

def foo(pool,head,result,n):
    """ pool, head and result should be lists, n a positive integer """
    if (n == 0):
       while (pool != []):
             head.append(pool.pop())
             result.append(head[:])
             head.pop()
    else:
       while (pool != []):
             head.append(pool.pop())
             foo(pool[:],head,result,n-1)
             head.pop()

def power(set):
    head = []
    result = [[]]
    for i in range(len(set)):
        foo(set[:],head,result,i)
    return result

This gives the subsets in a simmilar order to the one in which I would find 
them if I was doing it by hand, but its kind of difficult to think about, so 
I thought about it a bit more and came up with:

def power(set):
    result = []
    bits = len(set)
    for string in range(2**bits):
        subset = []
        position = 0
        while (string > 0):
              if (string % 2 != 0):
                 subset.append(set[position])
              string /= 2
              position += 1
        result.append(subset)
    return result

Even though this algorithm gives the subsets in a completely different order 
to the way I'd normally find them by hand, I'm guessing its closer to the 
"canonical" algorithm for finding power sets than my recursive attempt, am I 
right? or is there a third, completely different way of doing this?