[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:
http://www.nist.gov/dads/HTML/graycode.html
Gray code
(definition)
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
http://lib-www.lanl.gov/numerical/bookcpdf/c20-2.pdf
Enjoy!
/c