Recursion problem involving head, tail and xor

Question

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]

Answer 1

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.