# 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,

• 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]

-
Welcome! I am not sure this question suits this site; you are asking to figure out what a program computes without offering much of your own thought. What does g1 compute in general. –  Raphael Nov 27 '12 at 11:46
btw, what programming language is this? At first it looked like Python, but the endif statements and missing colons after the if statements clearly indicate it's not. –  Daniel Eberts Nov 27 '12 at 12:57
You are wrong : g1(n) = [ n mod 2 ] –  Anton Nov 27 '12 at 13:50
@DanielEberts this could be valid LUA code. –  Jan Dvorak Nov 27 '12 at 14:11