Definitions

# Tak (function)

Tak is a recursive mathematical function defined as

```def tak(x, y, z)
unless y < x
z
else
tak(
tak(x-1, y, z),
tak(y-1, z, x),
tak(z-1, x, y)
)
end
end
```

It is often used as a benchmark for languages with optimization for recursion.

## tak() vs. tarai()

Its original definition by Ikuo Takeuchi (竹内郁雄), however was as follows;

```def tarai(x, y, z)
unless y > x
y          # not z!
else
tarai(
tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y)
)
end
end
```

tarai is short for tarai mawashi, "to pass around" in Japanese.

John McCarthy attributed this function as tak() to commemorate Takeuchi but the y somehow got turned into the z.

This is a small, but significant difference because the original version benefits significantly by 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)
```

You can easily accelerate this function via memoization yet lazy evaluation still wins.

The best known way to optimize tarai is to use mutually recursive helper function as follows.

```def laziest_tarai(x, y, zx, zy, zz)
unless y < x
y
else
laziest_tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(zx, zy, zz)-1, x, y)
end
enddef tarai(x, y, z)
unless y < x
y
else
laziest_tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
z-1, x, y)
end
end
```

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 an additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.