Tak (function)

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

def tak -> int:
if y < x:
return tak,
tak,
tak
)
else:
return z

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 -> int:
if y < x:
return tarai,
tarai,
tarai
)
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.

tarai :: Int -> Int -> Int -> Int
tarai x y z
| x <= y = y
| otherwise = tarai

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 -> int:
if not y < x:
return y
else:
return laziest_tarai,
tarai,
tarai
def tarai -> int:
if not y < x:
return y
else:
return laziest_tarai,
tarai,
z-1, x, y)

Here is an efficient implementation of tarai in C:

int tarai

Note the additional check for before z is evaluated, avoiding unnecessary recursive evaluation.