Recursion challenge

[LooseCaboose]

Pseudo-code for iterative Gray code:

Code:

for i = 1 to n: a[i] = 0; d[i] = 1;
for i = 0 to n: up[i] = i;

do
  output();
  i = up[n];
  up[n] = n;
  a[i] = a[i] + d[i];
  up[i] = up[i - 1];
  up[i - 1] = i - 1;
  d[i] = -d[i];
loop until i = 0

a is the current Gray code, d is a direction array and the up array is used to jump across the tree to reduce the ammortized time to O(1). The recursive version is quite easy (but really difficult to analyse):

Code:

G(1) = {0, 1}
G(n) = 0G(n - 1)
     = 1G`(n - 1)

G`(1) = {1, 0}
G`(n) = 1G(n - 1)
      = 0G`(n - 1)