In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, the Tak function is a
recursive function, named after
Ikuo Takeuchi (竹内郁雄). 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
Benchmark may refer to:
Business and economics
* Benchmarking, evaluating performance within organizations
* Benchmark price
* Benchmark (crude oil), oil-specific practices
Science and technology
* Benchmark (surveying), a point of known elevati ...
for languages with optimization for
recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematic ...
.
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 たらい回し ''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 by
lazy evaluation
In programming language theory, lazy evaluation, or call-by-need, is an evaluation strategy which delays the evaluation of an expression until its value is needed ( non-strict evaluation) and which also avoids repeated evaluations ( sharing).
T ...
.
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 has pioneered a number of programming lan ...
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
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization ...
yet lazy evaluation still wins.
The best known way to optimize tarai is to use 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.
References
External links
*
TAK Function
{{Benchmark
Functions and mappings
Special functions