[Tutor] a recursion opportunity

Christopher Smith csmith@blakeschool.org
Wed, 06 Feb 2002 16:57:36 -0600

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.  (This would make a nice "stepping stone" exercise in a
series of exercises for beginning programmers.)  

The definition occurred in an article about Gray code:


Gray code


Definition: An ordering of 2^n binary numbers such that only one bit
changes from one entry to the next. 

Also known as grey code. 

See also Karnaugh map. 

Note: Gray codes are useful in mechanical encoders since a slight change
in location only affects one bit. Using a typical binary code, up to n
bits could change, and slight misalignments between reading elements could
cause wildly incorrect readings. 

One Gray code for 3 bits is (000, 010, 011, 001, 101, 111, 110, 100). Gray
codes are not unique. An n-bit Gray code corresponds to a Hamiltonian
cycle on an n-dimensional hypercube. 

One way to construct a Gray code for n bits is to take a Gray code for n-1
bits with each code prefixed by 0 (for the first half of the code) and
append the n-1 Gray code reversed with each code prefixed by 1 (for the
second half). 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

Gray codes were discovered by a French engineer Emile Baudot (1845-1903).
The codes were first patented by Frank Gray, a Bell Labs researcher, in
1953. (From Gray Codes). 

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.  If you've done a
permutation code already with recursion then you might think that this is
a "two base case" problem like I did (a case 0 and a case) but as I wrote
this I realized that it has a single base case, namely the Gray code for 0
bits which would be [''].

There is a nice discussion of Gray codes and their physical application to
mechanical devices at