In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, the Tak function is a
recursive function, named after . It is defined as follows:
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
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
.
tak() vs. tarai()
The original definition by Takeuchi was as follows:
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
In programming language theory, lazy evaluation, or call-by-need, is an evaluation strategy which delays the evaluation of an Expression (computer science), expression until its value is needed (non-strict evaluation) and which avoids repeated eva ...
.
Though written in exactly the same manner as others, the
Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
code below runs much faster.
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.
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:
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.
References
External links
*
TAK Function
{{Benchmark
Articles with example C code
Articles with example Haskell code
Articles with example Python (programming language) code
Functions and mappings
Special functions