Tak Function

Wednesday, July 23, 2025

The Tak function is a recursive function, named after Ikuo Takeuchi, used sometimes as a programming language benchmark. On the Concatenative Wiki, I noticed a page with concatenative implementations of the Tak function, and wanted to explore some different ways to build it in Factor.

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 y

Note: there are two variants of this function defined, some return z instead of y.

Some parameters cause an extremely large number of recursions. For example, tak(18, 12, 25) makes 76,527,789 function calls! Measuring the execution time demonstrates that:

In [23]: %time tak(18, 12, 25)
CPU times: user 1.79 s, sys: 4.89 ms, total: 1.79 s
Wall time: 1.79 s

Out [23]: 25

A direct translation of the Python code might look like this:

:: tak ( x y z -- result )
    y x < [
        x 1 - y z tak
        y 1 - z x tak
        z 1 - x y tak
        tak
    ] [ y ] if ;

And we can see that it works and is almost 6x faster than Python.

IN: scratchpad [ 18 12 25 tak ] time .
Running time: 0.307333458 seconds

25

But, we could get all stacky and build it like this:

: tak ( x y z -- result )
    2over > [
        [ [ 1 - ] 2dip tak ] 3keep
        [ [ 1 - ] dip rot tak ] 3keep
        1 - -rot tak tak
    ] [ drop nip ] if ;

Or, cleavy and build it like this:

: tak ( x y z -- result )
    2over > [
        {
            [ [ 1 - ] 2dip tak ]
            [ [ 1 - ] dip rot tak ]
            [ 1 - -rot tak ]
        } 3cleave tak
    ] [ drop nip ] if ;

Or, composey and build it like this:

: tak ( x y z -- result )
    2over > [
        [ ] [ rot ] [ -rot ] [ '[ @ [ 1 - ] 2dip tak ] ] tri@ 3tri tak
    ] [ drop nip ] if ;

Or, reduce some unnecessary recursion with a more efficient version:

:: tak ( x! y! z! -- result )
    [ x y > ] [
        x y :> ( oldx oldy )
        x 1 - y z tak x!
        y 1 - z oldx tak y!
        x y <= [ z 1 - oldx oldy tak z! ] unless
    ] while y ;

But, it turns out there is a simpler solution:

:: tak ( x y z -- result )
    {
        { [ y x >= ] [ y ] }
        { [ y z <= ] [ z ] }
        [ x ]
    } cond ;

Which could be written more concisely in one line:

:: tak ( x y z -- result )
    y x >= [ y ] [ y z <= z x ? ] if ;

And that is the fastest of all:

IN: scratchpad [ 18 12 25 tak ] time .
Running time: 0.000073916 seconds

25

Fun.