Так (функция)

В информатике функция Tak — это рекурсивная функция , названная в честь Икуо Такеучи ( ja:竹内郁雄 ). Оно определяется следующим образом:

$$\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

Эта функция часто используется в качестве эталона для языков с оптимизацией рекурсии .

так() против. тарай()

Первоначальное определение Такеучи было следующим:

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!

«тараи» — сокращение от «тараи маваси» , что по-японски означает «раздавать».

Джон Маккарти назвал эту функцию tak() в честь Такеучи.

Однако в некоторых более поздних источниках буква y каким-то образом превратилась в букву z. Это небольшая, но существенная разница, поскольку исходная версия значительно выигрывает от отложенных вычислений .

написан точно так же, как и другие, Хотя приведенный ниже код Haskell он работает намного быстрее.

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)

Эту функцию можно легко ускорить с помощью мемоизации , но ленивая оценка все равно побеждает.

Самый известный способ оптимизации tarai — использовать взаимно рекурсивную вспомогательную функцию следующим образом.

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)

Вот эффективная реализация tarai() в 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;
}

Обратите внимание на дополнительную проверку (x <= y) перед вычислением z (третьего аргумента), что позволяет избежать ненужных рекурсивных вычислений.

Внешние ссылки

• Вайсштейн, Эрик В. «Функция ТАК» . Математический мир .
• Функция ТАК