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

-
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

## 1 Answer

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.

-
Hi All, Thanks for your inputs. I am able to find what g2() returns. g2(n)= 0 if n is even and 1 if n is odd. – akshay Nov 28 '12 at 10:24