View source for Tak (function)

{{Short description|Recursive function}}
In [[computer science]], the '''Tak function''' is a [[Recursion (computer science)|recursive function]], named after {{Interlanguage link|Ikuo Takeuchi|ja|竹内郁雄|WD=}}. It is defined as follows:

<math display="block">
\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}
 </math>

<syntaxhighlight lang="python">
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
</syntaxhighlight>

This function is often used as a [[benchmark (computing)|benchmark]] for languages with optimization for [[recursion]].<ref>
{{cite journal | author=Peter Coffee| title=Tak test stands the test of time  | journal=PC Week| year=1996 | volume=13 |issue=39 }} 
</ref><ref>
[http://buildingblocksjava.com/recursive-methods/ "Recursive Methods"]
by Elliotte Rusty Harold
</ref><ref name="acornuser198606">{{ 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 }}</ref><ref name="acornuser198611">{{ 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 }}</ref>

==tak() vs. tarai()==
{{more sources|section|date=September 2023}}

The original definition by Takeuchi was as follows:

<syntaxhighlight lang="python">
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!
</syntaxhighlight>

tarai is short for {{Nihongo krt|"to pass around"|たらい回し|tarai mawashi}} in Japanese.

[[John McCarthy (computer scientist)|John McCarthy]] named this function tak() after Takeuchi.<ref>
{{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 }}
</ref>

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 (programming language)|Haskell]] code below runs much faster.

<syntaxhighlight lang="haskell">
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)
</syntaxhighlight>

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.

<syntaxhighlight lang="python">
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)
</syntaxhighlight>

Here is an efficient implementation of tarai() in C:
<syntaxhighlight lang="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;
}
</syntaxhighlight>
Note the additional check for (<code>x <= y</code>) 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]]
[[Category:Functions and mappings]]
[[Category:Special functions]]