Incomputer science, theTak function is arecursive function, named afterIkuo Takeuchi [ja]. It is defined as follows:
deftak(x:int,y:int,z:int)->int:ify<x:returntak(tak(x-1,y,z),tak(y-1,z,x),tak(z-1,x,y))else:returnz
This function is often used as abenchmark for languages with optimization forrecursion.[1][2][3][4]
 | This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "Tak" function – news ·newspapers ·books ·scholar ·JSTOR(September 2023) (Learn how and when to remove this message) |
The original definition by Takeuchi was as follows:
deftarai(x:int,y:int,z:int)->int:ify<x:returntarai(tarai(x-1,y,z),tarai(y-1,z,x),tarai(z-1,x,y))else:returny# not z!
tarai is short forたらい回し (tarai mawashi, "to pass around") in Japanese.
John McCarthy named this function tak() after Takeuchi.[5]
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 fromlazy evaluation.
Though written in exactly the same manner as others, theHaskell code below runs much faster.
tarai::Int->Int->Int->Inttaraixyz|x<=y=y|otherwise=tarai(tarai(x-1)yz)(tarai(y-1)zx)(tarai(z-1)xy)
One can easily accelerate this function viamemoization yet lazy evaluation still wins.
The best known way to optimize tarai is to use a mutually recursive helper function as follows.
deflaziest_tarai(x:int,y:int,zx:int,zy:int,zz:int)->int:ifnoty<x:returnyelse:returnlaziest_tarai(tarai(x-1,y,z),tarai(y-1,z,x),tarai(zx,zy,zz)-1,x,y)deftarai(x:int,y:int,z:int)->int:ifnoty<x:returnyelse:returnlaziest_tarai(tarai(x-1,y,z),tarai(y-1,z,x),z-1,x,y)
Here is an efficient implementation of tarai() in C:
inttarai(intx,inty,intz){while(x>y){intoldx=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);}returny;}
Note the additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.