En informática , la función Tak es una función recursiva , que lleva el nombre de Ikuo Takeuchi (ja:竹内郁雄). Se define de la siguiente manera:
def tak ( x , y , z ): si y < x : devolver tak ( tak ( x - 1 , y , z ), tak ( y - 1 , z , x ), tak ( z - 1 , x , y ) ) más : devolver zEsta función se utiliza a menudo como punto de referencia para lenguajes con optimización para recursividad . [1] [2] [3] [4]
La definición original de Takeuchi era la siguiente:
def tarai ( x , y , z ): si y < x : devuelve tarai ( tarai ( x - 1 , y , z ), tarai ( y - 1 , z , x ), tarai ( z - 1 , x , y ) ) más : devuelve y # no z!tarai es la abreviatura de たらい回しtarai mawashi , "pasar" en japonés.
John McCarthy nombró esta función tak() en honor a Takeuchi. [5]
Sin embargo, en ciertas referencias posteriores, la y de alguna manera se convirtió en z. Esta es una diferencia pequeña, pero significativa, porque la versión original se beneficia significativamente de la evaluación diferida .
Aunque está escrito exactamente de la misma manera que otros, el siguiente código de Haskell 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 auxiliar mutuamente recursiva de la siguiente manera.
def laziest_tarai ( x , y , zx , zy , zz ): si no y < x : devolver y else : devolver laziest_tarai ( tarai ( x - 1 , y , z ), tarai ( y - 1 , z , x ), tarai ( zx , zy , zz ) - 1 , x , y ) def tarai ( x , y , z ): si no y < x : devolver y sino : devolver laziest_tarai ( tarai ( x - 1 , y , z ), tarai ( y - 1 , z , x ), z - 1 , x , y ) 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 , viejox ); si ( x <= y ) romper ; z = tarai ( z - 1 , viejox , viejo ); } devolver y ; } Tenga en cuenta la verificación adicional de (x <= y) antes de que se evalúe z (el tercer argumento), evitando una evaluación recursiva innecesaria.