Tak (function)
In computer science, the Tak function is a recursive function, named after Ikuo Takeuchi (竹内郁雄). It is defined as follows:
def tak( x, y, z)
if y < x
tak(
tak(x-1, y, z),
tak(y-1, z, x),
tak(z-1, x, y)
)
else
z
end
end
This function is often used as a benchmark for languages with optimization for recursion.[1][2]
tak() vs. tarai()
The original definition by Takeuchi was as follows:
def tarai( x, y, z)
if y < x
tarai(
tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y)
)
else
y # not z!
end
end
tarai is short for tarai mawashi, "to pass around" in Japanese.
John McCarthy named this function tak() after Takeuchi.[3]
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. 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(tarai (x-1) y z)
(tarai (y-1) z x)
(tarai (z-1) x y)
You can easily accelerate this function via 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)
unless y < x
y
else
laziest_tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(zx, zy, zz)-1, x, y)
end
end
def tarai(x, y, z)
unless y < x
y
else
laziest_tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
z-1, x, y)
end
end
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 <= y) break;
z = tarai(z - 1, oldx, oldy);
}
return y;
}
Note the additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.
References
- ↑ Peter Coffee (1996). "Tak test stands the test of time". PC Week. 13 (39).
- ↑ "Recursive Methods" by Elliotte Rusty Harold
- ↑ John McCarthy (December 1979). "An Interesting LISP Function". ACM Lisp Bulletin (3): 6–8. doi:10.1145/1411829.1411833.