Recursion problem involving head, tail and xor Consider a set of functions:


head(l) returns first bit from list l, e.g.

head([0,1,0]) = 0, 
head([1]) = 1

tail(l) returns a list by removing first element from l, e.g. 

tail([0,1,0]) = [1,0],
tail([1]) = []

a:l appends bit a to beginning of list l, e.g.

1:[0,1,0] = [1,0,1,0].

xor takes takes as input two bits and returns a bit.

xor(a,b)
if (a == b) 
  return(0)
else 
  return(1)
endif

f1 takes as input a list and returns another list.

f1(s)
if (s == []) then 
  return([1])
else if (head(s) == 0) then  
  return(1:tail(s))
else if (head(s) == 1) then 
  return(0:f1(tail(s)))
endif



f2 takes as input a bit and a list and returns a bit.

f2(b,s)
if (s == []) then 
  return(b)
else if (head(s) == 0) then 
  return(f2(xor(b,1),tail(s)))
else if (head(s) == 1) then 
  return(xor(b,1))
endif

g1 takes as input a nonnegative number and returns a list.

g1(n)
if (n == 0) then 
  return([0])
else 
  return f1(g1(n-1))
endif

g2 takes as input a nonnegative number and returns a bit.

g2(n)
if (n == 0) then 
  return(0)
else 
  return f2(g2(n-1),g1(n))
endif



Can anyone explain what the function g2() returns?

I am able to find out g1() returns a list in binary
for example 

g1(1) = [1]
g1(2) = [01]
g1(3) = [11]
g1(4) = [001]
Hints:


g1(0) = [0] so you can see that f1 for [0] returns [1] and for [1] returns [0]. From here g1 must be clear.
f2 takes a bit and a list of one element and returns a bit so it is one of the boolean functions of 2 variables (they are only 16)
after you know that g2(0) = 0 and the above hints it is easier to calculate g2


I can propose you to post your answer or I will update my answer after some time to be sure that it was not for homework.