Tak (function)

In computer science, the Tak function is a recursive function, named after Ikuo Takeuchi (ja:竹内郁雄). It is defined as follows:

$$\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}}$$

<syntaxhighlight lang="python"> def tak(x, y, z):

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

</syntaxhighlight>

This function is often used as a benchmark for languages with optimization for recursion.

tak() vs. tarai()

The original definition by Takeuchi was as follows:

<syntaxhighlight lang="python"> def tarai(x, y, z):

   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!

</syntaxhighlight>

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

John McCarthy named this function tak() after Takeuchi.

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.

<syntaxhighlight lang="haskell"> tarai :: Int -> Int -> Int -> Int tarai x y z

   | x <= y    = y
   | otherwise = tarai (tarai (x-1) y z)
                       (tarai (y-1) z x)
                       (tarai (z-1) x y)

</syntaxhighlight>

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

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

<syntaxhighlight lang="ruby"> def laziest_tarai(x, y, zx, zy, zz):

   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)

def tarai(x, y, z):

   if not y < x:
       return y
   else:
       return laziest_tarai(
           tarai(x-1, y, z),
           tarai(y-1, z, x),
           z-1, x, y)

</syntaxhighlight>

Here is an efficient implementation of tarai() in C: <syntaxhighlight lang="c"> int tarai(int x, int y, int z) {

   while (x > y) {
       int oldx = 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);
   }
   return y;

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

External links

• Weisstein, Eric W. "TAK Function". MathWorld.
• TAK Function