Анонимная рекурсия
В информатике , анонимная рекурсия — это рекурсия которая не вызывает явную функцию по имени. Это можно сделать либо явно, используя функцию более высокого порядка (передав функцию в качестве аргумента и вызвав ее), либо неявно, с помощью функций отражения , которые позволяют получить доступ к определенным функциям в зависимости от текущего контекста, особенно «текущей функции». " или иногда "вызывающая функция текущей функции".
В практике программирования анонимная рекурсия особенно используется в JavaScript , который предоставляет средства отражения для ее поддержки. Однако в общей практике программирования это считается плохим стилем, и вместо этого предлагается рекурсия с именованными функциями. Анонимная рекурсия посредством явной передачи функций в качестве аргументов возможна на любом языке, поддерживающем функции в качестве аргументов, хотя на практике это используется редко, поскольку это длиннее и менее понятно, чем явная рекурсия по имени.
В теоретической информатике анонимная рекурсия важна, поскольку она показывает, что можно реализовать рекурсию, не требуя именованных функций. Это особенно важно для лямбда-исчисления , которое имеет анонимные унарные функции, но способно вычислить любую рекурсивную функцию. Эту анонимную рекурсию можно создать в общих чертах с помощью комбинаторов с фиксированной точкой .
Используйте [ править ]
Анонимная рекурсия в первую очередь используется для обеспечения рекурсии для анонимных функций , особенно когда они образуют замыкания или используются в качестве обратных вызовов , чтобы избежать необходимости привязывать имя функции.
Анонимная рекурсия в основном состоит из вызова «текущей функции», что приводит к прямой рекурсии . Возможна анонимная косвенная рекурсия , например, путем вызова «вызывающего объекта (предыдущей функции)» или, реже, путем перехода дальше вверх по стеку вызовов , и это можно объединить в цепочку для создания взаимной рекурсии . Самоссылка , «текущей функции» является функциональным эквивалентом ключевого слова « this » в объектно-ориентированном программировании позволяя ссылаться на текущий контекст.
Анонимную рекурсию также можно использовать для именованных функций, а не вызывать их по имени, например, чтобы указать, что выполняется рекурсия для текущей функции, или чтобы можно было переименовать функцию без необходимости изменять имя, в котором она вызывает себя. Однако в соответствии со стилем программирования этого обычно не делают.
Альтернативы [ править ]
Именованные функции [ править ]
Обычная альтернатива — использование именованных функций и именованной рекурсии. Учитывая анонимную функцию, это можно сделать либо путем привязки имени к функции, как в выражениях именованных функций в JavaScript, либо путем присвоения функции переменной и последующего вызова этой переменной, как в операторах функций в JavaScript. Поскольку языки, допускающие анонимные функции, обычно позволяют присваивать эти функции переменным (если не функциям первого класса), многие языки не предоставляют возможности ссылаться на саму функцию и явно отвергают анонимную рекурсию; примеры включают Go . [1]
Например, в JavaScript функция факториала может быть определена посредством анонимной рекурсии следующим образом: [2]
[1, 2, 3, 4, 5].map(function(n) {
return (!(n > 1)) ? 1 : arguments.callee(n-1) * n;
});
Переписано для использования выражения именованной функции, что дает:
[1, 2, 3, 4, 5].map(function factorial(n) {
return (!(n > 1)) ? 1 : factorial(n-1) * n;
});
Передача функций в качестве аргументов [ править ]
Даже без механизмов обращения к текущей функции или вызывающей функции анонимная рекурсия возможна в языке, который допускает функции в качестве аргументов. Это делается путем добавления еще одного параметра к базовой рекурсивной функции и использования этого параметра в качестве функции для рекурсивного вызова. Это создает функцию более высокого порядка, и передача этой функции более высокого порядка сама позволяет анонимную рекурсию внутри фактической рекурсивной функции. Это можно сделать чисто анонимно, применив к этой функции более высокого порядка комбинатор с фиксированной точкой . Это в основном представляет академический интерес, в частности, чтобы показать, что лямбда-исчисление имеет рекурсию, поскольку полученное выражение значительно сложнее, чем исходная названная рекурсивная функция. И наоборот, использование комбинаторов с фиксированной точкой можно в целом назвать «анонимной рекурсией», поскольку это их заметное использование, хотя у них есть и другие приложения. [3] [4]
Это показано ниже с использованием Python. Во-первых, стандартная именованная рекурсия:
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)
Использование функции более высокого порядка, чтобы функция верхнего уровня анонимно рекурсировала по аргументу, но при этом в качестве аргумента все равно требовалась стандартная рекурсивная функция:
def fact0(n0):
if n0 == 0:
return 1
return n0 * fact0(n0 - 1)
fact1 = lambda f, n1: 1 if n1 == 0 else n1 * f(n1 - 1)
fact = lambda n: fact1(fact0, n)
Мы можем исключить стандартную рекурсивную функцию, передав аргумент функции в вызов:
fact1 = lambda f, n1: 1 if n1 == 0 else n1 * f(f, n1 - 1)
fact = lambda n: fact1(fact1, n)
Вторую строку можно заменить общей функцией высшего порядка, называемой комбинатором :
F = lambda f: (lambda x: f(f, x))
fact1 = lambda f, n1: 1 if n1 == 0 else n1 * f(f, n1 - 1)
fact = F(fact1)
Написано анонимно: [5]
(lambda f: (lambda x: f(f, x))) \
(lambda g, n1: 1 if n1 == 0 else n1 * g(g, n1 - 1))
В лямбда-исчислении , которое использует только функции одной переменной, это можно сделать с помощью Y-комбинатора . Сначала сделайте функцию высшего порядка двух переменных функцией одной переменной, которая напрямую возвращает функцию, с помощью каррирования :
fact1 = lambda f: (lambda n1: 1 if n1 == 0 else n1 * f(f)(n1 - 1))
fact = fact1(fact1)
Здесь есть две операции «применения функции более высокого порядка к самой себе»: f(f) в первой строке и fact1(fact1) во втором. Вынесение второго двойного приложения в комбинатор дает:
C = lambda x: x(x)
fact1 = lambda f: (lambda n1: 1 if n1 == 0 else n1 * f(f)(n1 - 1))
fact = C(fact1)
Если исключить другое двойное приложение, получим:
C = lambda x: x(x)
D = lambda f: (lambda x: f(lambda v: x(x)(v)))
fact1 = lambda g: (lambda n1: 1 if n1 == 0 else n1 * g(n1 - 1))
fact = C(D(fact1))
Объединение двух комбинаторов в один дает комбинатор Y :
C = lambda x: x(x)
D = lambda f: (lambda x: f(lambda v: x(x)(v)))
Y = lambda y: C(D(y))
fact1 = lambda g: (lambda n1: 1 if n1 == 0 else n1 * g(n1 - 1))
fact = Y(fact1)
Раскрытие Y-комбинатора дает:
Y = lambda f: (lambda x: f(lambda v: x(x)(v))) \
(lambda x: f(lambda v: x(x)(v)))
fact1 = lambda g: (lambda n1: 1 if n1 == 0 else n1 * g(n1 - 1))
fact = Y(fact1)
Их объединение дает рекурсивное определение факториала в лямбда-исчислении (анонимные функции одной переменной): [6]
(lambda f: (lambda x: f(lambda v: x(x)(v)))
(lambda x: f(lambda v: x(x)(v)))) \
(lambda g: (lambda n1: 1 if n1 == 0 else n1 * g(n1 - 1)))
Примеры [ править ]
АПЛ [ править ]
В APL текущий dfn доступен через ∇. Это позволяет анонимную рекурсию, например, в этой реализации факториала:
{0=⍵:1 ⋄ ⍵×∇ ⍵-1} 5
120
{0=⍵:1 ⋄ ⍵×∇ ⍵-1}¨ ⍳10 ⍝ applied to each element of 0 to 9
1 1 2 6 24 120 720 5040 40320 362880
JavaScript [ править ]
В JavaScript текущая функция доступна через arguments.callee, а вызывающая функция доступна через arguments.caller. Они позволяют анонимную рекурсию, например, в этой реализации факториала: [2]
[1, 2, 3, 4, 5].map(function(n) {
return (!(n > 1)) ? 1 : arguments.callee(n - 1) * n;
});
Перл [ править ]
Начиная с Perl 5.16, текущая подпрограмма доступна через __SUB__ токен, который возвращает ссылку на текущую подпрограмму, или undef вне подпрограммы. [7] Это позволяет анонимную рекурсию, например, в следующей реализации факториала:
#!/usr/bin/perl
use feature ":5.16";
print sub {
my $x = shift;
$x > 0
? $x * __SUB__->( $x - 1 )
: 1;
}->(5), "\n";
Р [ править ]
В R текущую функцию можно вызвать с помощью Recall. Например,
sapply(0:5, function(n) {
if (n == 0) return(1)
n * Recall(n - 1)
})
Однако он не будет работать, если будет передан в качестве аргумента другой функции, например lapply, внутри определения анонимной функции. В этом случае, sys.function(0) можно использовать. [8] Например, приведенный ниже код рекурсивно возводит список в квадрат:
(function(x) {
if (is.list(x)) {
lapply(x, sys.function(0))
} else {
x^2
}
})(list(list(1, 2, 3), list(4, 5)))
Ссылки [ править ]
- ^ Проблема 226: невозможно рекурсивно выполнить анонимную функцию в Go без обходных путей.
- ^ Jump up to: Перейти обратно: а б ответ olliej, 25 октября 2008 г. на вопрос « Почему свойство аргументов.callee.caller устарело в JavaScript? », StackOverflow
- ^ Эта терминология, по-видимому, во многом фольклорная , но она встречается в следующем:
- Трей Нэш, Accelerated C# 2008 , Apress, 2007, ISBN 1-59059-873-3 , с. 462—463. В основном взято из Уэса Дайера (см. следующий пункт). блога
- Анонимная рекурсия Уэса Дайера в C# , 2 февраля 2007 г., содержит по существу аналогичный пример, найденный в книге выше, но сопровождаемый дополнительным обсуждением.
- ^ The If Works , вывод Y-комбинатора , 10 января 2008 г.
- ^ Ответ Хьюго Уолтера на вопрос « Может ли лямбда-функция рекурсивно вызывать себя в Python? »
- ^ Ответ Nux на вопрос « Может ли лямбда-функция рекурсивно вызывать себя в Python? »
- ^ Perldoc, « Функция current_sub» , функция perldoc
- ^ ответ agstudy на получение вызываемой в данный момент функции для написания анонимной рекурсивной функции в StackOverflow