Tak (function) explained

In computer science, the Tak function is a recursive function, named after . It is defined as follows:

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

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

tak vs. tarai

The original definition by Takeuchi was as follows:

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!

tarai is short for 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 -> Inttarai x y z | x <= y = y | otherwise = tarai (tarai (x-1) y z) (tarai (y-1) z x) (tarai (z-1) x y)

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.

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)

Here is an efficient implementation of tarai in C:int tarai(int x, int y, int z)Note the additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.

External links

• • TAK Function

Notes and References

1. Peter Coffee. Tak test stands the test of time . PC Week. 1996 . 13 . 39 .
2. http://buildingblocksjava.com/recursive-methods/ "Recursive Methods"
3. News: Six of the Best Against the Clock . Acorn User . June 1986 . 28 October 2020 . Johnson-Davies . David . 179, 181–182 .
4. News: Testing the Tak . Acorn User . November 1986 . 28 October 2020 . Johnson-Davies . David . 197, 199 .
5. John McCarthy . An Interesting LISP Function . ACM Lisp Bulletin . December 1979 . 3 . 6–8 . 10.1145/1411829.1411833. 31639459 .