Анонимная рекурсия - Anonymous recursion
В информатике , анонимные рекурсии являются рекурсией , не явно вызывать функцию по имени. Это может быть сделано либо явно, используя функцию более высокого порядка - передавая функцию в качестве аргумента и вызывая ее, - либо неявно, с помощью функций отражения, которые позволяют получить доступ к определенным функциям в зависимости от текущего контекста, особенно «текущая функция "или иногда" вызывающая функция текущей функции ".
В практике программирования анонимная рекурсия особенно используется в JavaScript , который предоставляет средства отражения для ее поддержки. Однако в общей практике программирования это считается плохим стилем, и вместо него предлагается рекурсия с именованными функциями. Анонимная рекурсия посредством явной передачи функций в качестве аргументов возможна на любом языке, который поддерживает функции в качестве аргументов, хотя на практике это редко используется, поскольку оно длиннее и менее понятно, чем явное рекурсирование по имени.
В теоретической информатике важна анонимная рекурсия, поскольку она показывает, что можно реализовать рекурсию, не требуя именованных функций. Это особенно важно для лямбда-исчисления , которое имеет анонимные унарные функции, но может вычислять любую рекурсивную функцию. Эта анонимная рекурсия может быть произведена в общем с помощью комбинаторов с фиксированной точкой .
Использовать
Анонимная рекурсия в первую очередь используется для разрешения рекурсии для анонимных функций , особенно когда они образуют замыкания или используются в качестве обратных вызовов , чтобы избежать необходимости связывать имя функции.
Анонимная рекурсия в первую очередь состоит из вызова «текущей функции», что приводит к прямой рекурсии . Возможна анонимная косвенная рекурсия , например, путем вызова «вызывающего (предыдущая функция)» или, что реже, путем продвижения вверх по стеку вызовов , и это может быть связано для создания взаимной рекурсии . Само -ссылка «текущей функции» является функциональным эквивалентом ключевого слова « this » в объектно-ориентированном программировании , позволяя ссылаться на текущий контекст.
Анонимная рекурсия также может использоваться для именованных функций, а не для их вызова по имени, скажем, чтобы указать, что одна из них рекурсивно выполняет текущую функцию, или чтобы позволить переименовать функцию без необходимости изменять имя, в котором она вызывает себя. Однако с точки зрения стиля программирования этого обычно не происходит.
Альтернативы
Именованные функции
Обычная альтернатива - использовать именованные функции и именованную рекурсию. Для анонимной функции это можно сделать либо путем привязки имени к функции, как в выражениях именованных функций в JavaScript, либо путем присвоения функции переменной и последующего вызова этой переменной, как в операторах функции в JavaScript. Поскольку языки, которые разрешают анонимные функции, обычно позволяют назначать эти функции переменным (если не первоклассным функциям), многие языки не предоставляют способ ссылки на саму функцию и явно отвергают анонимную рекурсию; примеры включают Go .
Например, в JavaScript факториальную функцию можно определить через анонимную рекурсию как таковую:
[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;
});
Передача функций в качестве аргументов
Даже без механизмов для ссылки на текущую функцию или вызывающую функцию анонимная рекурсия возможна на языке, который допускает функции в качестве аргументов. Это делается путем добавления другого параметра к базовой рекурсивной функции и использования этого параметра в качестве функции для рекурсивного вызова. Это создает функцию более высокого порядка, а сама передача этой функции позволяет анонимную рекурсию внутри фактической рекурсивной функции. Это можно сделать чисто анонимно, применив комбинатор с фиксированной точкой к этой функции более высокого порядка. Это в основном представляет академический интерес, особенно для того, чтобы показать, что лямбда-исчисление имеет рекурсию, поскольку результирующее выражение значительно сложнее, чем исходная именованная рекурсивная функция. И наоборот, использование комбинаторов с фиксированной точкой можно в общем называть «анонимной рекурсией», так как это заметное их использование, хотя у них есть и другие приложения.
Это показано ниже с использованием 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)
Написано анонимно:
(lambda f: (lambda x: f(f, x))) \
(lambda g, n1: 1 if n1 == 0 else n1 * g(g, n1 - 1))
В лямбда - исчислении , который использует только функции одной переменной, это может быть сделано через Y Combinator . Сначала сделайте функцию высшего порядка двух переменных функцией одной переменной, которая напрямую возвращает функцию, путем каррирования :
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)
Их объединение дает рекурсивное определение факториала в лямбда-исчислении (анонимные функции одной переменной):
(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
В 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. Они позволяют анонимную рекурсию, например, в этой реализации факториала:
[1, 2, 3, 4, 5].map(function(n) {
return (!(n > 1)) ? 1 : arguments.callee(n - 1) * n;
});
Perl
Начиная с Perl 5.16, текущая подпрограмма доступна через __SUB__токен, который возвращает ссылку на текущую подпрограмму, или undefвне подпрограммы. Это позволяет анонимную рекурсию, например, в следующей реализации факториала:
#!/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)можно использовать. Например, приведенный ниже код рекурсивно возводит список в квадрат:
(function(x) {
if (is.list(x)) {
lapply(x, sys.function(0))
} else {
x^2
}
})(list(list(1, 2, 3), list(4, 5)))