Takeuchi function

The Takeuchi function is a triply recursive 3-parameter function originally defined by Ichiro Takeuchi in 1978 as $t(x,y,z)=y$ if $x\le y$ and $t(x,y,z)=t(t(x-1,y,z),t(y-1,z,x),t(z-1,x,y))$ otherwise. Later John McCarthy simplified the definition of the function as $t(x,y,z)=y$ if $x\le y$, $t(x,y,z)=z$ if $y\le z$ and $t(x,y,z)=x$ in all other cases.

For example, $t(194,13,5)=194$ since 194 is not less than 13, and 13 is not less than 5. The return value of the function “is on no practical significance,” but the function itself “is useful for benchmark testing of programming languages.” (Finch, 2003) The function $T(x,y,z)$ is the number of times $t$ calls itself to obtain the return value. A properly optimized implementation of the function in a given programming language should not require more recursion than $T$ indicates.