TAK Function

A Recursive Function devised by I. Takeuchi. For Integers $x$, $y$, and $z$, and a function $h$, it is

$${\rm TAK}_h(x,y,z)=\cases{ h(x,y,z) & for $x\leq y$\cr {\rm ... ...$x>y$.\cr \quad {\rm TAK}_h(y-1,z,x),{\rm TAK}_h(z-1,x,y))\cr}$$

The number of function calls $F_0(a,b)$ required to compute ${\rm TAK}_0(a,b,0)$ for $a>b>0$ is

$$F_0(a,b)=4\sum_{k=0}^b {a-b\over a+b-2k}{a+b-2k\choose b-k}-3 = 1+4\sum_{k=0}^{b-1} {a-b\over a+b-2k}{a+b-2k\choose b-k}$$

(Vardi 1991).

The TAK function is also connected with the Ballot Problem (Vardi 1991).

See also Ackermann Function, Ballot Problem

References

Gabriel, R. P. Performance and Implementation of Lisp Systems. Cambridge, MA: MIT Press, 1985.

Knuth, D. E. Textbook Examples of Recursion. Preprint 1990.

Vardi, I. ``The Running Time of TAK.'' Ch. 9 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 179-199, 1991.