[Tutor] Bit Strings [a recursive approach]

[Blake Winton]

> def bitstrings(n):
>     if n == 0: return []
>     if n == 1: return ["0","1"]
>     return [ digit+bitstring for digit in bitstrings(1)
>                              for bitstring in bitstrings(n-1) ]

Along those lines, I've always thought that n=0 should
really return [""].  Which could make the function into:
###
def bitstrings(n):
    if n == 0: return [""]
    return [ digit+bitstring for digit in ["0","1"]
                             for bitstring in bitstrings(n-1) ]
###
(I prefer to use the explicit list ["0","1"] for the digits
 to avoid yet another call to the bitstrings function, and
 to avoid having to define what bitstrings(1) should return.
 But that's probably just me.)

And of course, this opens up the whole can of worms of how we
should represent emptyness, and what the proper result of
bitstrings(0) should really be.  As a mathematician, I seem
to remember that there's one way to choose 0 numbers out of
a set, and so the array returned by bitstrings(0) should
really contain one element.  It also makes for a nice regularity
as demonstrated in the following code:

###
for x in xrange(5):
    print x, len( bitstrings(x) )
###
0 1
1 2
2 4
3 8
4 16
###

If we special-case n=0 to return [], then the size of the list
returned by bitstrings(n) is no longer 2**n.  Just a thought.

Later,
Blake.