[Tutor] Bit Strings [a recursive approach]

[Timothy M. Brauch]

Whilst trying to find all bit strings of a certain length, I struggled.
Danny Yoo was helpful with:

> Have you tried a recursive approach?  It might be useful to outline how to
> solve this recursively, so here goes!  *grin*

I should have thought of this, since the way I was doing it by hand was
basically recursive...

> >>> def appendInFront(x, L):
> ...     return [x + element for element in L]
> ...
> >>> appendInFront("0", bitstrings(2))
> ['000', '001', '010', '011']
> ###
...
> Here's the punchline: things will work if we take a leap of faith, and
> just write:
>
> ###
> def bitstrings(n):
>     if n == 0: return []
>     if n == 1: return ["0", "1"]
>     if n == 2: return ["00", "01", "10", "11"]
>     else:
>         return (appendInFront("0", bitstrings(n-1))
>                 + appendInFront("1", bitstrings(n-1)))
> ###
>
>
> Does this make sense so far?  Please feel free to ask questions on this.

Yes, that is the way I was doing it by hand.  First right down the n=1 case.
Then for n=2, write it down a second time and put a zero in front of the
first half, a 1 in front of the second half.  For n=3, write down n=2 twice,
putting a 0 infront of the first half, a 1 in front of the second...

I guess I just didn't realize what I was doing by hand would have worked if
I had coded it correctly.  And, the nice thing about this is that it should
be pretty easy to extend the idea if my strings need to have more
characters.  Just a few more base cases and the else:return needs to be have
a few more lines. Thanks.

 - Timothy

P.S. I guess it is the mathematician in me that doesn't like recursively
defined functions.  We tend to like closed form things better.  And it was
my stumbling block in my algorithm classes.  Although, recursive is often
much more elegant...



---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.528 / Virus Database: 324 - Release Date: 10/17/2003