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

В інформатиці анонімна рекурсія є рекурсією, у якій не використовується виклик функції по імені. Це може бути зроблено або явно, використовуючи функцію більш високого порядку - передаючи функцію як аргумент і викликаючи її, - чи неявно, за допомогою можливостей рефлексії, які дозволяють отримати доступ до певних функцій поточного ^[en], наприклад "поточну функцію", або "функцію що викликала поточну функцію".

У теоретичній інформатиці важлива анонімна рекурсія, оскільки вона показує, що можна реалізувати рекурсію, не вимагаючи іменованих функцій. Це особливо важливо для лямбда-числення, яке має анонімні унарні функції, але може обчислювати будь-яку рекурсивную функцію. Ця анонімна рекурсія може бути проведена в загальному за допомогою ^[en].

Використання

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

Анонімна рекурсія в основному складається з виклику «поточної функції», що призводить до прямої рекурсії. Можлива анонімна непряма рекурсія, наприклад, шляхом виклику функції, що викликає (попередня функція) або, рідше, шляхом просування ще вище по стеку викликів.

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

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

Іменовані функції

Типова альтернатива - використовувати іменовані функції і іменовану рекурсію. Для анонімної функції це можна зробити або шляхом прив'язки імені до функції, як у виразах іменованих функцій в 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; }); 

Передача функцій як аргументів

Навіть без механізмів посилання на поточну функцію або функцію що її викликає, анонімна рекурсія можлива в мовах яка дозволяє функції як аргументи. Це робиться шляхом додавання іншого параметра до основної рекурсивної функції та використання цього параметра як функції для рекурсивного виклику. Це створює функцію вищого порядку, і передача цієї функції як аргумент самій собі дозволяє анонімну рекурсію в межах фактичної рекурсивної функції.

Це можна зробити повністю анонімно, застосувавши до цієї функції вищого порядку ^[en]. Це головним чином представляє академічний інтерес, особливо для того, щоб показати, що лямбда-числення має рекурсію, оскільки отриманий вираз значно складніший, ніж вихідна іменована рекурсивна функція. І навпаки, використання комбінаторів з нерухомою точкою загалом може називатися "анонімною рекурсією", оскільки це є найвідомішим їх використанням, хоча вони мають і інші застосування.

Продемонструємо це нижче, мовою Python. Спершу, стандартна іменована рекурсія:

def fact(n): if n == 0: return 1 return n * fact(n - 1) 

Використовуючи функцію вищого порядку, що отримує сама себе як аргумент:

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)) 

В лямбда-численні, яке використовує тільки функції однієї змінної, це може бути зроблено через . Спочатку створимо функцію вищого порядку двох змінних функцією однієї змінної, яка безпосередньо повертає функцію за допомогою каррінгу:

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 поточна ^[en] доступна через ∇. Це дозволяє анонімну рекурсію, наприклад, у цій реалізації факторіалу:

 {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

У 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))) 

Див. також

• Рекурсія
• Анонімна функція

Зноски

1. arguments.callee - JavaScript. MDN. 7 вересня 2023. Процитовано 11 лютого 2024.
2. . Архів оригіналу за 8 березня 2014. Процитовано 15 листопада 2020.
3. answer by olliej, Oct 25 '08 to "Why was the arguments.callee.caller property deprecated in JavaScript?", StackOverflow
4. * Trey Nash, Accelerated C# 2008, Apress, 2007, , p. 462—463. Derived substantially from Wes Dyer's blog (see next item).
   • Wes Dyer Anonymous Recursion in C# [ 18 січня 2010 у Wayback Machine.], February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion.
5. The If Works Deriving the Y combinator [ 26 серпня 2009 у Wayback Machine.], January 10th, 2008
6. Відповідь Hugo Walter-са на питання "Can a lambda function call itself recursively in Python?"
7. Nux's answer to "Can a lambda function call itself recursively in Python?"
8. Function.prototype.caller - JavaScript | MDN. MDN. 12 квітня 2023. Процитовано 11 лютого 2024.