[Tutor] a recursion opportunity

[Gregor Lingl]

----- Original Message -----
From: "Christopher Smith" <csmith@blakeschool.org>
To: <tutor@python.org>
Sent: Wednesday, February 06, 2002 11:57 PM
Subject: [Tutor] a recursion opportunity


> I was reading about Boolean algebra today and happened across a nice
> little recursion definition that anyone wanting to sharpen up on recursion
> might want to try.  ...
> Here is an example of creating a 3-bit Gray code from a
> 2-bit Gray code.
>
> 00 01 11 10 A Gray code for 2 bits
> 000 001 011 010 the 2-bit code with "0" prefixes
> 10 11 01 00 the 2-bit code in reverse order
> 110 111 101 100 the reversed code with "1" prefixes
> 000 001 011 010 110 111 101 100 A Gray code for 3 bits
> ...
> So the exercise is to write a function that will return a list of strings
> representing the binary numbers in an n-bit Gray code.

To break the silence, this is my solution:

def gray(l):
    if l:
        return ['0'+l[0]] + gray(l[1:]) + ['1'+l[0]]
    else:
        return []

def graycode(n):
    if n:
        return gray(graycode(n-1))
    else:
        return ['']

I'm interested in yours. Can it be done in ONE SINGLE recursive function?
Gregor