Tak (function)

In computer science, the Tak function is a recursive function, named after Ikuo Takeuchi [ja ]. It is defined as follows:

$${\displaystyle \tau (x,y,z)={\begin{cases}\tau (\tau (x-1,y,z),\tau (y-1,z,x),\tau (z-1,x,y))&{\text{if }}y<x\\z&{\text{otherwise}}\end{cases}}}$${\displaystyle \tau (x,y,z)={\begin{cases}\tau (\tau (x-1,y,z),\tau (y-1,z,x),\tau (z-1,x,y))&{\text{if }}y<x\\z&{\text{otherwise}}\end{cases}}}

deftak(x: int, y: int, z: int) -> int:
 if y < x:
 return tak( 
 tak(x - 1, y, z),
 tak(y - 1, z, x),
 tak(z - 1, x, y)
 )
 else:
 return z

This function is often used as a benchmark for languages with optimization for recursion.^{[1] [2] [3] [4]}

The original definition by Takeuchi was as follows:

deftarai(x: int, y: int, z: int) -> int:
 if y < x:
 return tarai( 
 tarai(x - 1, y, z),
 tarai(y - 1, z, x),
 tarai(z - 1, x, y)
 )
 else:
 return y # not z!

tarai is short for たらい回し (tarai mawashi, "to pass around") in Japanese.

John McCarthy named this function tak() after Takeuchi.^[5]

However, in certain later references, the y somehow got turned into the z. This is a small, but significant difference because the original version benefits significantly from lazy evaluation.

Though written in exactly the same manner as others, the Haskell code below runs much faster.

tarai::Int->Int->Int->Int
taraixyz
|x<=y=y
|otherwise=tarai(tarai(x-1)yz)
(tarai(y-1)zx)
(tarai(z-1)xy)

One can easily accelerate this function via memoization yet lazy evaluation still wins.

The best known way to optimize tarai is to use a mutually recursive helper function as follows.

deflaziest_tarai(x: int, y: int, zx: int, zy: int, zz: int) -> int:
 if not y < x:
 return y
 else:
 return laziest_tarai(
 tarai(x-1, y, z),
 tarai(y-1, z, x),
 tarai(zx, zy, zz)-1, x, y)
deftarai(x: int, y: int, z: int) -> int:
 if not y < x:
 return y
 else:
 return laziest_tarai(
 tarai(x-1, y, z),
 tarai(y-1, z, x),
 z-1, x, y)

Here is an efficient implementation of tarai() in C:

inttarai(intx,inty,intz)
{
while(x>y){
intoldx=x,oldy=y;
x=tarai(x-1,y,z);
y=tarai(y-1,z,oldx);
if(x<=y)break;
z=tarai(z-1,oldx,oldy);
}
returny;
}

Note the additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.

• Weisstein, Eric W. "TAK Function". MathWorld .
• TAK Function Archived 2007年09月12日 at the Wayback Machine