---
title: Tak (function)
slug: tak-function
qid: 
snapshot: enwiki-001301932557
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1301932557
tags: [23081986, 23603337, 23837581, 24043274, 24623845, 25257581, 26220375, 29176345, 29176629, 32509203, 36473759]
---

# Tak (function)

> [!note] Provenance
> Snapshot `enwiki-001301932557` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1301932557> · Licensed CC BY-SA 4.0

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 def tak(x: int, y: int, z: int) -> int: if y This function is often used as a benchmark for languages with optimization for recursion.

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 def tak(x: int, y: int, z: int) -> int: if y This function is often used as a benchmark for languages with optimization for recursion. ==tak() vs. tarai()== The original definition by Takeuchi was as follows: def tarai(x: int, y: int, z: int) -> int: if y 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 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 int: if not 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 Note the additional check for ( x ) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation. ==References== ==External links== TAK Function
