Misplaced Pages

In computer science, the Tak function is a recursive function, named after Ikuo Takeuchi [ja]. It is defined as follows:

$${\displaystyle \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, 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 for languages with optimization for recursion.

tak() vs. tarai()

This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "Tak" function – news · newspapers · books · scholar · JSTOR (September 2023) (Learn how and when to remove this message)

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 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, 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)
{
    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

1. Peter Coffee (1996). "Tak test stands the test of time". PC Week. 13 (39).
2. "Recursive Methods" by Elliotte Rusty Harold
3. Johnson-Davies, David (June 1986). "Six of the Best Against the Clock". Acorn User. pp. 179, 181–182. Retrieved 28 October 2020.
4. Johnson-Davies, David (November 1986). "Testing the Tak". Acorn User. pp. 197, 199. Retrieved 28 October 2020.
5. John McCarthy (December 1979). "An Interesting LISP Function". ACM Lisp Bulletin (3): 6–8. doi:10.1145/1411829.1411833. S2CID 31639459.

External links

• Weisstein, Eric W. "TAK Function". MathWorld.
• TAK Function

• Functions and mappings
• Special functions