Так (функция) - Tak (function)

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

def так( Икс, у, z)  если у < Икс    так(          так(Икс-1, у, z),         так(у-1, z, Икс),         так(z-1, Икс, у)       )  еще    z  конецконец

Эта функция часто используется как ориентир для языков с оптимизацией для рекурсия.[1][2][3][4]

tak () vs. tarai ()

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

def тарай( Икс, у, z)  если у < Икс    тарай(          тарай(Икс-1, у, z),         тарай(у-1, z, Икс),         тарай(z-1, Икс, у)       )  еще    у          # не z!  конецконец

тарай - это сокращение от тараи маваши, "разойтись" на японском.

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

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

тарай :: Int -> Int -> Int -> Intтарай Икс у z    | Икс <= у    = у    | иначе = тарай(тарай (Икс-1) у z)                       (тарай (у-1) z Икс)                       (тарай (z-1) Икс у)

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

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

def laziest_tarai(Икс, у, zx, зы, zz)  пока не у < Икс    у  еще    laziest_tarai(тарай(Икс-1, у, z),                  тарай(у-1, z, Икс),                  тарай(zx, зы, zz)-1, Икс, у)  конецконецdef тарай(Икс, у, z)  пока не у < Икс    у  еще    laziest_tarai(тарай(Икс-1, у, z),                  тарай(у-1, z, Икс),                  z-1, Икс, у)  конецконец

Вот эффективная реализация tarai () на C:

int тарай(int Икс, int у, int z){    пока (Икс > у) {        int Oldx = Икс, старый = у;        Икс = тарай(Икс - 1, у, z);        у = тарай(у - 1, z, oldx);        если (Икс <= у) перемена;        z = тарай(z - 1, Oldx, старый);    }    возвращаться у;}

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

Рекомендации

  1. ^ Питер Кофе (1996). «Так тест выдерживает испытание временем». Неделя ПК. 13 (39).
  2. ^ «Рекурсивные методы» Эллиотт Расти Гарольд
  3. ^ Джонсон-Дэвис, Дэвид (июнь 1986). «Шесть лучших против времени». Желудь Пользователь. С. 179, 181–182. Получено 28 октября 2020.
  4. ^ Джонсон-Дэвис, Дэвид (ноябрь 1986). «Тестирование так». Желудь Пользователь. С. 197, 199. Получено 28 октября 2020.
  5. ^ Джон Маккарти (декабрь 1979 г.). «Интересная функция LISP». Бюллетень ACM Lisp (3): 6–8. Дои:10.1145/1411829.1411833.

внешняя ссылка