Анонимная рекурсия - Anonymous recursion

В Информатика, анонимная рекурсия является рекурсия который не вызывает явно функцию по имени. Это можно сделать либо явно, используя функция высшего порядка - передача функции в качестве аргумента и ее вызов - или неявно через отражение особенности, которые позволяют получить доступ к определенным функциям в зависимости от текущего контекста, особенно к «текущей функции» или иногда к «вызывающей функции текущей функции».

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

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

Использовать

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

Анонимная рекурсия в первую очередь состоит из вызова «текущей функции», что приводит к прямая рекурсия. Анонимный косвенная рекурсия возможно, например, путем вызова «вызывающего (предыдущая функция)» или, что реже, путем перехода вверх по стек вызовов, и это можно связать, чтобы произвести взаимная рекурсия. В ссылка на себя слова "текущая функция" является функциональным эквивалентом "это "ключевое слово в объектно-ориентированного программирования, позволяя ссылаться на текущий контекст.

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

Альтернативы

Именованные функции

Обычная альтернатива - использовать именованные функции и именованную рекурсию. Для анонимной функции это можно сделать либо путем привязки имени к функции, как в выражениях именованных функций в JavaScript, либо путем присвоения функции переменной и последующего вызова этой переменной, как в операторах функции в JavaScript. Поскольку языки, которые разрешают анонимные функции, обычно позволяют назначать эти функции переменным (если не первоклассным функциям), многие языки не предоставляют способ ссылки на саму функцию и явно отвергают анонимную рекурсию; примеры включают Идти.[1]

Например, в JavaScript факториальную функцию можно определить через анонимную рекурсию как таковую:[2]

[1, 2, 3, 4, 5].карта(функция(п) {     возвращаться (!(п > 1)) ? 1 : аргументы.вызываемый(п-1) * п;});

Переписанный для использования именованного выражения функции дает:

[1, 2, 3, 4, 5].карта(функция факториал(п) {     возвращаться (!(п > 1)) ? 1 : факториал(п-1) * п;});

Передача функций в качестве аргументов

Даже без механизмов для ссылки на текущую функцию или вызывающую функцию анонимная рекурсия возможна на языке, который допускает функции в качестве аргументов. Это делается путем добавления другого параметра к базовой рекурсивной функции и использования этого параметра в качестве функции для рекурсивного вызова. Это создает функцию более высокого порядка и передает эту функцию более высокого уровня сам позволяет анонимную рекурсию внутри фактической рекурсивной функции. Это можно сделать анонимно, применив комбинатор с фиксированной точкой к этой функции высшего порядка. Это в основном представляет академический интерес, особенно для того, чтобы показать, что лямбда-исчисление имеет рекурсию, поскольку результирующее выражение значительно сложнее, чем исходная именованная рекурсивная функция. И наоборот, использование комбинаторов с фиксированной точкой можно в общем называть «анонимной рекурсией», так как это заметное их использование, хотя у них есть и другие приложения.[3][4]

Это показано ниже с использованием Python. Во-первых, стандартная именованная рекурсия:

def факт(п):    если п == 0:        возвращаться 1    возвращаться п * факт(п - 1)

Использование функции высшего порядка для анонимной рекурсии функции верхнего уровня по аргументу, но при этом для использования стандартной рекурсивной функции в качестве аргумента:

def факт0(n0):    если n0 == 0:        возвращаться 1    возвращаться n0 * факт0(n0 - 1)факт1 = лямбда ж, n1: 1 если n1 == 0 еще n1 * ж(n1 - 1)факт = лямбда п: факт1(факт0, п)

Мы можем исключить стандартную рекурсивную функцию, передав аргумент функции в вызов:

факт1 = лямбда ж, n1: 1 если n1 == 0 еще n1 * ж(ж, n1 - 1)факт = лямбда п: факт1(факт1, п)

Вторую строку можно заменить общей функция высшего порядка называется комбинатор:

F = лямбда ж: (лямбда Икс: ж(ж, Икс))факт1 = лямбда ж, n1: 1 если n1 == 0 еще n1 * ж(ж, n1 - 1)факт = F(факт1)

Написано анонимно:[5]

(лямбда ж: (лямбда Икс: ж(ж, Икс))) \(лямбда грамм, n1: 1 если n1 == 0 еще n1 * грамм(грамм, n1 - 1))

в лямбда-исчисление, который использует только функции одной переменной, это можно сделать с помощью Y комбинатор. Сначала сделайте функцию высшего порядка двух переменных функцией одной переменной, которая напрямую возвращает функцию, с помощью карри:

факт1 = лямбда ж: (лямбда n1: 1 если n1 == 0 еще n1 * ж(ж)(n1 - 1))факт = факт1(факт1)

Здесь есть две операции "применения функции высшего порядка к самой себе": f (f) в первой строке и факт1 (факт1) В секунду. Разложив второе двойное приложение на комбинатор дает:

C = лямбда Икс: Икс(Икс)факт1 = лямбда ж: (лямбда n1: 1 если n1 == 0 еще n1 * ж(ж)(n1 - 1))факт = C(факт1)

Без учета другого двойного внесения дает:

C = лямбда Икс: Икс(Икс)D = лямбда ж: (лямбда Икс: ж(лямбда v: Икс(Икс)(v)))факт1 = лямбда грамм: (лямбда n1: 1 если n1 == 0 еще n1 * грамм(n1 - 1))факт = C(D(факт1))

Объединение двух комбинаторов в один дает Y комбинатор:

C = лямбда Икс: Икс(Икс)D = лямбда ж: (лямбда Икс: ж(лямбда v: Икс(Икс)(v)))Y = лямбда у: C(D(у))факт1 = лямбда грамм: (лямбда n1: 1 если n1 == 0 еще n1 * грамм(n1 - 1))факт = Y(факт1)

Расширение комбинатора Y дает:

Y = лямбда ж: (лямбда Икс: ж(лямбда v: Икс(Икс)(v))) \              (лямбда Икс: ж(лямбда v: Икс(Икс)(v)))факт1 = лямбда грамм: (лямбда n1: 1 если n1 == 0 еще n1 * грамм(n1 - 1))факт = Y(факт1)

Их объединение дает рекурсивное определение факториала в лямбда-исчислении (анонимные функции одной переменной):[6]

(лямбда ж: (лямбда Икс: ж(лямбда v: Икс(Икс)(v)))           (лямбда Икс: ж(лямбда v: Икс(Икс)(v)))) \(лямбда грамм: (лямбда n1: 1 если n1 == 0 еще n1 * грамм(n1 - 1)))

Примеры

APL

В APL, электрический ток dfn доступен через ∇. Это позволяет анонимную рекурсию, например, в этой реализации факториала:

   {0=⍵:1 ⋄ ⍵×∇ ⍵-1} 5120   {0=⍵:1 ⋄ ⍵×∇ ⍵-1}¨ ⍳10    ⍝ применяется к каждому элементу от 0 до 91 1 2 6 24 120 720 5040 40320 362880

JavaScript

В JavaScript, текущая функция доступна через arguments.callee, а вызывающая функция доступна через arguments.caller. Они позволяют анонимную рекурсию, например, в этой реализации факториала:[2]

[1, 2, 3, 4, 5].карта(функция(п) {    возвращаться (!(п > 1)) ? 1 : аргументы.вызываемый(п - 1) * п;});

Perl

Начиная с Perl 5.16, текущая подпрограмма доступна через __SUB__ токен, который возвращает ссылку на текущую подпрограмму, или undef вне подпрограммы.[7] Это позволяет анонимную рекурсию, например, в следующей реализации факториала:

#! / usr / bin / perlиспользовать особенность ":5.16";Распечатать суб {    мой $ x = сдвиг;    $ x > 0    ? $ x * __SUB__->( $ x - 1 )    : 1;}->(5), " п";

р

В р, текущую функцию можно вызвать с помощью Отзывать. Например,

сочный(0:5, функция(п) {  если (п == 0) возвращаться(1)  п * Отзывать(п - 1)})

Однако это не сработает, если передать его в качестве аргумента другой функции, например. ласковыйвнутри определения анонимной функции. В этом случае, sys.function (0) может быть использован.[8] Например, приведенный ниже код рекурсивно возводит список в квадрат:

(функция(Икс) {  если (is.list(Икс)) {    ласковый(Икс, sys.function(0))  } еще {    х ^ 2  }})(список(список(1, 2, 3), список(4, 5)))

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

  1. ^ Проблема 226. Невозможно рекурсировать анонимную функцию в Go без обходных путей.
  2. ^ а б отвечать автор: olliej, 25 окт. 2008 г. по "Почему свойство arguments.callee.caller устарело в JavaScript? ", Переполнение стека
  3. ^ Эта терминология в значительной степени фольклор, но он появляется в следующем:
    • Трей Нэш, Ускоренный C # 2008, Апресс, 2007, г. ISBN  1-59059-873-3, п. 462–463. В значительной степени получено из Уэс Дайер блог пользователя (см. следующий пункт).
    • Уэс Дайер Анонимная рекурсия в C #, 2 февраля 2007 г., содержит по существу аналогичный пример из вышеприведенной книги, но с дополнительным обсуждением.
  4. ^ Если работает Получение комбинатора Y, 10 января 2008 г.
  5. ^ Ответ Хьюго Уолтера к "Может ли лямбда-функция вызывать себя рекурсивно в Python? "
  6. ^ Ответ Нукса к "Может ли лямбда-функция вызывать себя рекурсивно в Python? "
  7. ^ Перлдок "Функция 'current_sub' ", функция perldoc
  8. ^ ответ agstudy к Получить текущую вызываемую функцию для записи анонимной рекурсивной функции в Переполнение стека