Tak (function)
{{Short description|Recursive function}}
In computer science, the Tak function is a recursive function, named after {{Interlanguage link|Ikuo Takeuchi|ja|竹内郁雄|WD=}}. 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 < x \\
z & \text{otherwise}
\end{cases}
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.
{{cite journal | author=Peter Coffee| title=Tak test stands the test of time | journal=PC Week| year=1996 | volume=13 |issue=39 }}
[http://buildingblocksjava.com/recursive-methods/ "Recursive Methods"]
by Elliotte Rusty Harold
{{ cite news | url=https://archive.org/details/AcornUser047-Jun86/page/n180/mode/1up | title=Six of the Best Against the Clock | work=Acorn User | date=June 1986 | accessdate=28 October 2020 | last1=Johnson-Davies | first1=David | pages=179, 181–182 }}{{ cite news | url=https://archive.org/details/AcornUser052-Nov86/page/n198/mode/1up | title=Testing the Tak | work=Acorn User | date=November 1986 | accessdate=28 October 2020 | last1=Johnson-Davies | first1=David | pages=197, 199 }}
tak() vs. tarai()
{{more sources|section|date=September 2023}}
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 {{Nihongo krt|"to pass around"|たらい回し|tarai mawashi}} in Japanese.
John McCarthy named this function tak() after Takeuchi.
{{cite journal | author=John McCarthy | title=An Interesting LISP Function | journal=ACM Lisp Bulletin |date=December 1979 | issue=3 | pages=6–8 | doi=10.1145/1411829.1411833| s2cid=31639459 }}
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 (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)
{
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
{{Reflist}}
External links
- {{mathworld|title=TAK Function|urlname=TAKFunction}}
- [http://www.nue.org/nue/#tak-function TAK Function]
{{Benchmark}}
Category:Articles with example C code
Category:Articles with example Haskell code
Category:Articles with example Python (programming language) code