I am given the following function as a brain teaser:
def t(x, y, z): if x <= z: return y else: return t(t(x - 1 , y , z ) , t(y - 1 , z , x ) , t (z - 1 , x , y ))
the task is to remove the recursion in the else-branch. the only allowed expressions are of type arithmetic (+,-,*,/,%), logical (&&,||,!), relational (<,<=,==,>=,>,!=) and if-else.
My first approach was to order the input in lexicographical order and trying to deduce a relationship which seemed to look like like this initially:
else: if y > x return x else: return z
but that does not work, a counterexample is
t(20, 7, 18)=8. So the underlying relationship seems to be a bit more complex. I have also tried to formally infer the solution by differentiating the cases for the '>'-relation between the variables but I did not get far with that either.