Recursive function
In computer science , the Tak function is a recursive function , named after Ikuo Takeuchi [ja ] . It is defined as follows:
τ τ -->
(
x
,
y
,
z
)
=
{
τ τ -->
(
τ τ -->
(
x
− − -->
1
,
y
,
z
)
,
τ τ -->
(
y
− − -->
1
,
z
,
x
)
,
τ τ -->
(
z
− − -->
1
,
x
,
y
)
)
if
y
<
x
z
otherwise
{\displaystyle \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<x\\z&{\text{otherwise}}\end{cases}}}
def tak ( x , y , z ):
if y < x :
return tak (
tak ( x - 1 , y , z ),
tak ( y - 1 , z , x ),
tak ( z - 1 , x , y )
)
else :
return z
This function is often used as a benchmark for languages with optimization for recursion .[ 1] [ 2] [ 3] [ 4]
tak() vs. tarai()
The original definition by Takeuchi was as follows:
def tarai ( x , y , z ):
if y < x :
return tarai (
tarai ( x - 1 , y , z ),
tarai ( y - 1 , z , x ),
tarai ( z - 1 , x , y )
)
else :
return y # 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 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 <= y = y
| otherwise = tarai ( tarai ( x - 1 ) y z )
( tarai ( y - 1 ) z x )
( tarai ( z - 1 ) x y )
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 , y , zx , zy , zz ):
if not y < x :
return y
else :
return laziest_tarai (
tarai ( x - 1 , y , z ),
tarai ( y - 1 , z , x ),
tarai ( zx , zy , zz ) - 1 , x , y )
def tarai ( x , y , z ):
if not y < x :
return y
else :
return laziest_tarai (
tarai ( x - 1 , y , z ),
tarai ( y - 1 , z , x ),
z - 1 , x , 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 <= y ) break ;
z = tarai ( z - 1 , oldx , oldy );
}
return y ;
}
Note the additional check for (x <= y
) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.
References
External links
Concepts Organizations Processor
Peripherals
Computer system (entire) Energy consumption Software
Platform specific