Tak (function)

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

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.[1][2][3][4]

tak() vs. tarai()

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.[5]

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.