[Tutor] Bit Strings [a recursive approach]

[Danny Yoo]

> >And in fact you could even remove the if n== 2 line. It works just fine
> >using the appendInFRont function!
> >
> >def bitstrings(n):
> >     if n == 0: return []
> >     if n == 1: return ["0", "1"]
> >     else:
> >         return (appendInFront("0", bitstrings(n-1))
> >                 + appendInFront("1", bitstrings(n-1)))

> May I supply another flavourof the recursive approach, which even
> doesn't need appendInFront (but incorporagtes it itself)? It's
> nevertheless very compact:
>
>  >>> def bitstrings(n):
>         if n==0: return ["0","1"]
>         return [ digit+bitstring for digit in bitstrings(1)
>                                  for bitstring in bitstrings(n-1)]

Hi Gregor,

Correction: the basis here needs to be repaired for n == 1;  otherwise,
this won't terminate.  With a recursive approach, we have to especially
careful about the boundary cases of our problem.


One way to fix the bug might be:

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


Good luck!