# Removing recursion from a function with multiple params

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.

Here is an equivalent way to calculate $$t(x,y,z)$$.

We distinguish between three cases:

1. $$x \leq z$$: the answer is $$y$$.

2. $$x = z + 1$$: the answer is $$z$$ if $$y \leq x$$, and $$x$$ otherwise.

3. $$x-z \geq 2$$: the answer is $$z$$ (if $$x-z$$ is odd) or $$\min(y+1,z)$$ (if $$x-z$$ is even) if $$y \leq x+1$$, and $$x$$ (if $$y-x$$ is even) or $$z+1$$ (if $$y-x$$ is odd) otherwise.

You should be able to prove this characterization by induction. The second case is identical to the third case, except that the condition $$y \leq x$$ is replaced by the condition $$y \leq x+1$$.

• yes thats it, thanks! tbh, I don't even know how to approach multidimensional induction (I was not even sure if it is applicable to this question), but I will try to figure it out by reading some sources. How long did it take you to get to the solution? – Doflaminhgo Nov 19 '19 at 9:58
• It took about an hour. I looked at the sequences $t(x,0,z),t(x,1,z),\ldots$ for various small values of $x,z$, and the pattern was obvious. – Yuval Filmus Nov 19 '19 at 11:28
• okay, based on your last comment I managed to find a slightly more verbose solution compared to yours, which should be equivalent (no min-function, but more if-elses). I honestly don't see how it's obvious though, it took me a couple hours and I probably could not even have done it, if I didn't glance at your solution beforehand (the odd-even-relations were difficult for me to spot). So thanks again! – Doflaminhgo Nov 19 '19 at 22:06