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

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

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

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

Используйте [ редактировать ]

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

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

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

Альтернативы [ править ]

Именованные функции [ править ]

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

Например, в JavaScript функция факториала может быть определена с помощью анонимной рекурсии как таковая: ^[2]

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

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

[ 1 ,  2 ,  3 ,  4 ,  5 ]. map ( функция  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 :  факт1 ( факт0 ,  п )

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

fact1  =  lambda  f ,  n1 :  1  если  n1  ==  0  else  n1  *  f ( f ,  n1  -  1 ) fact  =  lambda  n :  fact1 ( fact1 ,  n )

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

F  =  лямбда  f :  ( лямбда  x :  f ( f ,  x )) fact1  =  лямбда  f ,  n1 :  1,  если  n1  ==  0,  иначе  n1  *  f ( f ,  n1  -  1 ) fact  =  F ( fact1 )

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

( лямбда  f :  ( лямбда  x :  f ( f ,  x ))) \ ( лямбда  g ,  n1 :  1,  если  n1  ==  0,  иначе  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  =  лямбда  x :  x ( x ) fact1  =  lambda  f :  ( лямбда  n1 :  1,  если  n1  ==  0,  иначе  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( факт1 ))

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

C  =  лямбда  x :  x ( x ) D  =  лямбда  f :  ( лямбда  x :  f ( лямбда  v :  x ( x ) ( v ))) Y  =  лямбда  y :  C ( D ( y )) fact1  =  лямбда  g :  ( лямбда  n1 :  1,  если  n1  ==  0,  иначе  n1  * g ( n1  -  1 )) fact  =  Y ( fact1 )

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

Y  =  лямбда  f :  ( лямбда  x :  f ( лямбда  v :  x ( x ) ( v ))) \ ( лямбда  x :  f ( лямбда  v :  x ( x ) ( v ))) fact1  =  лямбда  g :  ( лямбда  n1 :  1,  если  n1  ==  0,  иначе  n1  *  g ( n1 -  1 )) факт  =  Y ( факт1 )

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

( лямбда  f :  ( лямбда  x :  f ( лямбда  v :  x ( x ) ( v )))  ( лямбда  x :  f ( лямбда  v :  x ( x ) ( v )))) \ ( лямбда  g :  ( лямбда  n1 :  1,  если  n1  ==  0  иначе  n1  *  g ( n1  -  1 )))

Примеры [ править ]

APL [ править ]

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

 { 0 = ⍵: 1  ⋄  ⍵ × ∇  ⍵ - 1 }  5 120  { 0 = ⍵: 1  ⋄  ⍵ × ∇  ⍵ - 1 } ¨  ⍳ 10  ⍝ применяется к каждому элементу от 0 до 9 1  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 use  feature  ": 5.16" ;напечатать  sub  {  мой  $ x  =  shift ;  $ x  >  0  ?  $ x  *  __SUB__ -> (  $ x  -  1  )  :  1 ; } -> ( 5 ),  «\ n» ;

R [ править ]

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

sapply ( 0 : 5 ,  function ( n )  {  if ( n  ==  0 )  return ( 1 )  n  *  Recall ( n  -  1 ) })

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

( функция ( x )  {  if ( is.list ( x ))  {  lapply ( x ,  sys.function ( 0 ))  }  else  {  x ^ 2  } }) ( список ( список ( 1 ,  2 ,  3 ),  список ( 4 ,  5 )))

Ссылки [ править ]