Surf Wiki
Save to docs
general/articles-with-example-c-code

From Surf Wiki (app.surf) — the open knowledge base

Tak (function)

Recursive function

Recursive function

In computer science, the Tak function is a recursive function, named after . 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 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. "Recursive Methods" by Elliotte Rusty Harold

tak() vs. tarai()

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 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
                        (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

References

References

  1. (June 1986). "Six of the Best Against the Clock". Acorn User.
  2. (November 1986). "Testing the Tak". Acorn User.
Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

articles-with-example-c-code articles-with-example-haskell-code articles-with-example-python-(programming-language)-code functions-and-mappings special-functions
Want to explore this topic further?

Ask Mako anything about Tak (function) — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report