Tak (function)

---

title: "Tak (function)" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["articles-with-example-c-code", "articles-with-example-haskell-code", "articles-with-example-python-(programming-language)-code", "functions-and-mappings", "special-functions"] description: "Recursive function" topic_path: "general/articles-with-example-c-code" source: "https://en.wikipedia.org/wiki/Tak_(function)" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Recursive function ::

In computer science, the Tak function is a recursive function, named after . 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 z & \text{otherwise} \end{cases}

::code[lang=python] def tak(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. "Recursive Methods" by Elliotte Rusty Harold

tak() vs. tarai()

The original definition by Takeuchi was as follows:

::code[lang=python] def tarai(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 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.

::code[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) ::

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.

::code[lang=python] def laziest_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)

def tarai(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: ::code[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; } ::

Note the additional check for (`x

References

References

1. (June 1986). "Six of the Best Against the Clock". Acorn User.
2. (November 1986). "Testing the Tak". Acorn User.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::