Tak (function)
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 def tak(x: int, y: int, z: int) -> int: if y This function is often used as a benchmark for languages with optimization for recursion.
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 def tak(x: int, y: int, z: int) -> int: if y 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: def tarai(x: int, y: int, z: int) -> int: if y 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. tarai :: Int -> Int -> Int -> Int tarai x y z | x 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: int, y: int, zx: int, zy: int, zz: int) -> int: if not y int: if not y Here is an efficient implementation of tarai() in 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 Note the additional check for ( x ) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.
References
External links
TAK Function
Text derived from https://en.wikipedia.org/w/index.php?oldid=1301932557 under CC BY-SA 4.0; modifications have been made.