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