Tak (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 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 REFERENCES ---------- BIBLIOGRAPHY (BibTeX) -------------------- @article{ref0, title = {Tak (function)}, url = {https://encyclopegia.org/a/tak-function} } BIBLIOGRAPHY (RIS) ------------------- TY - JOUR TI - Tak (function) UR - https://encyclopegia.org/a/tak-function ER - CITE THIS ARTICLE ---------------- Cite this article: Tak (function) Derived from: https://en.wikipedia.org/w/index.php?oldid=1301932557 Licence: CC BY-SA 4.0 Snapshot: enwiki-001301932557 Permalink: /a/tak-function