En informática , la función Tak es una función recursiva , que lleva el nombre de Ikuo Takeuchi (竹 内 郁 雄). Se define de la siguiente manera:
def tak ( x , y , z ) si y < x tak ( tak ( x - 1 , y , z ), tak ( y - 1 , z , x ), tak ( z - 1 , x , y ) ) más z fin fin
Esta función se utiliza a menudo como punto de referencia para lenguajes con optimización para recursividad . [1] [2] [3] [4]
tak () frente a tarai ()
La definición original de Takeuchi fue la siguiente:
def tarai ( x , y , z ) si y < x tarai ( tarai ( x - 1 , y , z ), tarai ( y - 1 , z , x ), tarai ( z - 1 , x , y ) ) más y # no z! fin fin
tarai es la abreviatura de た ら い 回 しtarai mawashi , "pasar" en japonés.
John McCarthy nombró a esta función tak () en honor a Takeuchi. [5]
Sin embargo, en ciertas referencias posteriores, la y de alguna manera se convirtió en la z. Esta es una diferencia pequeña, pero significativa, porque la versión original se beneficia significativamente de la evaluación perezosa . Aunque está escrito exactamente de la misma manera que otros, el código de Haskell a continuación se ejecuta mucho más rápido.
tarai :: Int -> Int -> Int -> Int tarai x y z | x <= y = y | de lo contrario = tarai ( tarai ( x - 1 ) y z ) ( tarai ( y - 1 ) z x ) ( tarai ( z - 1 ) x y )
Se puede acelerar fácilmente esta función mediante la memorización, pero la evaluación perezosa sigue ganando.
La forma más conocida de optimizar tarai es utilizar la función de ayuda recursiva mutua de la siguiente manera.
def laziest_tarai ( x , y , zx , zy , zz ) a menos que y < x y else laziest_tarai ( tarai ( x - 1 , y , z ), tarai ( y - 1 , z , x ), tarai ( zx , zy , zz ) - 1 , x , y ) fin findef tarai ( x , y , z ) a menos que y < x y else laziest_tarai ( tarai ( x - 1 , y , z ), tarai ( y - 1 , z , x ), z - 1 , x , y ) end end
Aquí hay una implementación eficiente de tarai () en 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 , antiguox ); si ( x <= y ) romper ; z = tarai ( z - 1 , oldx , oldy ); } return y ; }
Tenga en cuenta la verificación adicional para (x <= y) antes de que se evalúe z (el tercer argumento), evitando una evaluación recursiva innecesaria.
Referencias
- ^ Peter Coffee (1996). "Tak test resiste la prueba del tiempo". Semana de la PC . 13 (39).
- ^ "Métodos recursivos" por Elliotte Rusty Harold
- ^ Johnson-Davies, David (junio de 1986). "Seis de los mejores contrarreloj" . Usuario de bellota . págs. 179, 181-182 . Consultado el 28 de octubre de 2020 .
- ^ Johnson-Davies, David (noviembre de 1986). "Probando el Tak" . Usuario de bellota . págs. 197, 199 . Consultado el 28 de octubre de 2020 .
- ^ John McCarthy (diciembre de 1979). "Una función LISP interesante". Boletín ACM Lisp (3): 6–8. doi : 10.1145 / 1411829.1411833 .