익명 재귀

컴퓨터 과학에서 익명 재귀는 함수를 명시적으로 이름으로 호출하지 않는 재귀입니다.이것은 명시적으로, 인수로 함수를 전달하고 호출함으로써, 또는 현재 컨텍스트에 따라 특정 함수, 특히 "현재 함수" 또는 "현재 함수의 호출 함수"에 액세스할 수 있는 반사 기능을 통해 암묵적으로 수행될 수 있습니다.

프로그래밍 연습에서 익명 재귀는 JavaScript에서 특히 사용되며, 이를 지원하기 위한 반사 기능을 제공합니다.그러나 일반적인 프로그래밍 연습에서는 이는 잘못된 스타일로 간주되며 대신 명명된 함수를 사용한 재귀가 권장됩니다.함수를 인수로 명시적으로 전달하는 익명 재귀는 함수를 인수로 지원하는 모든 언어에서 가능하지만 이름으로 명시적으로 재귀하는 것보다 길고 명확하지 않기 때문에 실제로는 거의 사용되지 않습니다.

이론 컴퓨터 과학에서 익명 재귀는 이름 있는 함수를 필요로 하지 않고도 재귀를 구현할 수 있다는 것을 보여주기 때문에 중요합니다.이것은 익명 단항 함수를 가지지만 재귀 함수를 계산할 수 있는 람다 미적분에 특히 중요합니다.이 익명 재귀는 고정 소수점 조합기를 통해 일반적으로 생성될 수 있습니다.

사용하다

어나니머스 재귀는 주로 어나니머스 함수의 재귀(특히 함수의 이름을 바인딩할 필요가 없도록 닫힘을 형성하거나 콜백으로 사용되는 경우)를 허용하는 데 사용됩니다.

익명 재귀는 주로 "현재 함수"를 호출하여 직접 재귀로 이어집니다.「발신자(이전 함수)」를 호출하는 등, 또는 드물게 콜 스택의 한층 더 상위에의 호출에 의해서, 익명 간접 재귀가 가능하게 되어, 이것을 체인으로 해 상호 재귀를 발생시킬 수 있습니다."current function"의 자기 참조는 객체 지향 프로그래밍에서 "this" 키워드와 동일한 함수이며, 현재 컨텍스트를 참조할 수 있습니다.

익명 재귀는 이름 있는 함수에도 사용할 수 있습니다.예를 들어 이름으로 호출하는 함수에는 현재 함수에서 재귀하고 있음을 지정하거나 함수 자체를 호출하는 이름을 변경하지 않고 함수 이름을 변경할 수 있습니다.그러나 프로그래밍 스타일에 따라 이것은 일반적으로 수행되지 않습니다.

대체 수단

명명된 함수

일반적으로 이름 있는 함수와 이름 있는 재귀 기능을 사용하는 방법이 있습니다.어나니머스 함수는 자바스크립트의 이름 있는 함수 표현식처럼 함수에 이름을 바인딩하거나 자바스크립트의 함수 문처럼 함수를 변수에 할당하고 변수를 호출함으로써 수행할 수 있습니다.익명 함수를 허용하는 언어는 일반적으로 이러한 함수를 변수에 할당할 수 있으므로(일류 함수는 아닐지라도) 많은 언어는 함수 자체를 참조할 수 있는 방법을 제공하지 않으며 익명 재귀는 명시적으로 거부합니다. 예를 들어 ^[1]Go가 있습니다.

예를 들어 JavaScript에서는 다음과 ^[2]같이 익명 재귀를 통해 요인 함수를 정의할 수 있습니다.

[1, 2, 3, 4, 5].지도(기능.(n) {      돌아가다 (!(n > 1)) ? 1 : 논쟁들.착신자(n-1) * n; }); 

명명된 함수식을 사용하도록 다시 작성됨:

[1, 2, 3, 4, 5].지도(기능. 요인(n) {      돌아가다 (!(n > 1)) ? 1 : 요인(n-1) * n; }); 

함수를 인수로 전달

현재 함수나 호출 함수를 참조하는 메커니즘이 없어도 함수를 인수로 사용할 수 있는 언어에서는 익명 재귀가 가능합니다.이를 수행하려면 기본 재귀 함수에 다른 파라미터를 추가하고 이 파라미터를 재귀 호출의 함수로 사용합니다.그러면 고차 함수가 생성되며, 이 고차 함수 자체를 전달하면 실제 재귀 함수 내에서 익명 재귀가 허용됩니다.이것은 이 고차 함수에 고정 소수점 조합기를 적용함으로써 순전히 익명으로 실행할 수 있습니다.이것은 특히 람다 미적분에 재귀가 있다는 것을 보여주는 학문적인 관심사인데, 그 결과는 원래 이름 붙여진 재귀 함수보다 훨씬 복잡하기 때문이다.반대로, 고정점 결합기의 사용은 일반적으로 "익명 재귀"라고 불릴 수 있는데, 이는 다른 ^[3][4]응용 프로그램이 있지만 이러한 결합기의 주목할 만한 사용이기 때문입니다.

이것은 Python을 사용한 그림입니다.먼저 재귀라는 이름의 표준입니다.

방어하다 사실(n):     한다면 n == 0:         돌아가다 1     돌아가다 n * 사실(n - 1) 

상위 함수를 사용하여 최상위 함수가 인수로 익명으로 반복되지만 표준 재귀 함수는 인수로 계속 필요합니다.

방어하다 팩트0(n0):     한다면 n0 == 0:         돌아가다 1     돌아가다 n0 * 팩트0(n0 - 1) 팩트1 = 람다 f, n1: 1 한다면 n1 == 0 또 다른 n1 * f(n1 - 1) 사실 = 람다 n: 팩트1(팩트0, n) 

function 인수를 호출에 전달함으로써 표준 재귀 함수를 제거할 수 있습니다.

팩트1 = 람다 f, n1: 1 한다면 n1 == 0 또 다른 n1 * f(f, n1 - 1) 사실 = 람다 n: 팩트1(팩트1, n) 

두 번째 줄은 콤비네이터라고 하는 일반적인 고차 함수로 대체할 수 있습니다.

F = 람다 f: (람다 x: f(f, x)) 팩트1 = 람다 f, n1: 1 한다면 n1 == 0 또 다른 n1 * f(f, n1 - 1) 사실 = F(팩트1) 

익명으로 ^[5]작성:

(lsda f: (lsda x: f(f, x))) \ (n1 == 0이면 n1 x g(g, n1 - 1)

단일 변수의 함수만 사용하는 람다 미적분에서는 Y 결합기를 통해 이 작업을 수행할 수 있습니다.먼저 두 변수의 고차 함수를 단일 변수의 함수로 만들고 함수를 직접 반환합니다.

팩트1 = 람다 f: (람다 n1: 1 한다면 n1 == 0 또 다른 n1 * f(f)(n1 - 1)) 사실 = 팩트1(팩트1) 

여기에서는, 다음의 2개의 「고차 함수를 그 자체에 적용하는 방법은 다음과 같습니다.f(f)맨 앞줄에서fact1(fact1)두 번째에.두 번째 이중 애플리케이션을 조합기에 포함시키면 다음과 같은 결과가 나옵니다.

C = 람다 x: x(x) 팩트1 = 람다 f: (람다 n1: 1 한다면 n1 == 0 또 다른 n1 * f(f)(n1 - 1)) 사실 = C(팩트1) 

다른 2배의 어플리케이션의 산출량을 고려하면 다음과 같습니다.

C = 람다 x: x(x) D = 람다 f: (람다 x: f(람다 v: x(x)(v))) 팩트1 = 람다 g: (람다 n1: 1 한다면 n1 == 0 또 다른 n1 * g(n1 - 1)) 사실 = C(D(팩트1)) 

2개의 콤비네이터를 1개로 조합하면 Y콤비네이터가 생성됩니다.

C = 람다 x: x(x) D = 람다 f: (람다 x: f(람다 v: x(x)(v))) Y = 람다 y: C(D(y)) 팩트1 = 람다 g: (람다 n1: 1 한다면 n1 == 0 또 다른 n1 * g(n1 - 1)) 사실 = Y(팩트1) 

Y combinator를 확장하면 다음과 같이 산출됩니다.

Y = 람다 f : (lambda x : f(lambda v : x(x)(v))) \ (lambda x: f(lambda v: x(x)(v))) fact1 = 람다 g: (n1 == 0 else n1 * g(n1 - 1) fact = Y(1) fact (1) fact

이러한 요소를 결합하면 람다 미적분(단일 변수의 ^[6]익명 함수)에서 요인에 대한 재귀적 정의가 생성됩니다.

(7000da f: (7000da x: f(7000da v: x(x)(v)))) (7000da x: f(7000da v: x(x)(v))) \ (n1 == 0 else 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에서 현재 함수는 다음을 통해 액세스할 수 있습니다.arguments.callee콜링 함수는 를 통해 액세스 할 수 있습니다.arguments.caller이 요인 구현에서와 같은 ^[2]익명 재귀가 허용됩니다.

[1, 2, 3, 4, 5].지도(기능.(n) {     돌아가다 (!(n > 1)) ? 1 : 논쟁들.착신자(n - 1) * n; }); 

펄

Perl 5.16 이후 현재 서브루틴에는__SUB__token: 현재 서브루틴에 대한 참조를 반환합니다.undef서브루틴 ^[7]외부에 있습니다.이를 통해 다음과 같은 요인 구현과 같은 익명 재귀가 허용됩니다.

#!/usr/bin/module 사용하다 특징 ":5.16";  인쇄물 후보선수 {     나의 x달러 = 교대하다;     x달러 > 0     ? x달러 * __SUB__->( x달러 - 1 )     : 1; }->(5), "\n"; 

R

R에서 현재 함수는 다음을 사용하여 호출할 수 있습니다.Recall.예를들면,

엷은(0:5, 기능.(n) {   한다면(n == 0) 돌아가다(1)   n * 리콜(n - 1) }) 

단, 예를 들어 다른 함수에 인수로 전달되는 경우에는 작동하지 않습니다.lapply, 어나니머스 함수 정의 내에 있습니다.이 경우,sys.function(0)사용할 ^[8]수 있습니다.예를 들어, 아래 코드는 목록을 재귀적으로 제곱합니다.

(기능.(x) {   한다면(is.list(x)) {     느릿느릿(x, 시스템 기능(0))   } 또 다른 {     x^2   } })(목록.(목록.(1, 2, 3), 목록.(4, 5))) 

레퍼런스