{
  "id": "enwiki-001301932557",
  "slug": "tak-function",
  "title": "Tak (function)",
  "qid": "",
  "lead": "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.",
  "body": "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",
  "categories": [
    "23081986",
    "23603337",
    "23837581",
    "24043274",
    "24623845",
    "25257581",
    "26220375",
    "29176345",
    "29176629",
    "32509203",
    "36473759"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1301932557",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1753181901.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001301932557",
    "type": "webpage",
    "title": "Tak (function)",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/tak-function",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001301932557",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1301932557",
    "note": "Immutable snapshot enwiki-001301932557"
  }
}