# 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, 2012 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. Nov 27, 2012 at 12:57
• You are wrong : g1(n) = [ n mod 2 ] Nov 27, 2012 at 13:50
• @DanielEberts this could be valid LUA code. Nov 27, 2012 at 14:11