# The Beauty of Recursion

I was trying to write a snippet of code to generate all the subsets of a given set, in python. My thoughts were along the following lines:

• Have a number run from 0 to 2^n – 1 where n is the number of elements in the set.
• In each run, look at the binary representation of the number and select all the elements from the list whose corresponding bits (w.r.t their positions) are set to 1.
• At the end, return this list of lists, which is the power set.

The code looks like this:

```def getBinaryString(i):
'''
returns the binary format of i in string format
'''

if i == 0 or i == 1:
return str(i)

binary = ""
while i > 0:
binary = binary + str(i%2)
i = i/2

return binary

def getListSubset(L, i):
"""
Takes i and returns the corresponding elements in the binary
representation of i
"""

ithSubset = []
if i == 0:
return []

binary = getBinaryString(i)
#    print "binary string is: " + binary
length = 0
while length < len(binary):
if binary[length] == '1':
ithSubset.append(L[length])
length += 1

return ithSubset

def generateAllSubsets(L):
"""
Returns a list of all subsets of L
"""
allSubSets = []
listLen = len(L)
i = 0

#    print listLen
while i < 2 ** listLen:
aSubset = getListSubset(L, i)
allSubSets.append(aSubset[:])
i += 1

print "Total number of subsets: " + str(len(allSubSets))
return allSubSets
```

Its not that bad a piece of code, after all, but still, it is not as elegant as this beautiful recursive version:

When I looked at the recursive version, it just blew me out. I was convinced that thinking recursively is an art and beauty belies it.

```def genRecursiveSubsets(L):
'''
generates all the subsets recursively (i.e. beautifully)!
'''
if len(L) == 0:
return [[]]

smaller = genRecursiveSubsets(L[:-1])
extra = L[-1:]

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

return new + smaller
```