J: 재귀
J: 재귀 (Intro 22)
J 입문 22장에서는 재귀 정의(recursive definition)와 케이스 문, 자기 참조 $:를 설명해요. 계승과 하노이 탑을 예로 들어요.
출처: 문서
본문
계승 함수 !은 보통 factorial n 은 n 곱하기 factorial n-1 이라는 진술과, factorial 0 은 1 이라는 추가 진술로 정의돼요. 정의 중인 함수가 그 정의에서 다시 나타나므로(intend recurse) 이런 정의를 재귀적(recursive)이라 불러요.
케이스 문(case statement)을 사용해 재귀 정의를 만들 수 있어요. 정의 중인 함수를 사용하는 케이스가 종결 케이스(terminating case)를 만날 때까지 반복 선택돼요. 예를 들어:
factorial=: 1:`(]*factorial@<:) @. *
factorial "0 i.6
1 1 2 6 24 120
1:은 그 결과가 1인 상수 함수를 나타냄을 주목하세요.
문장 (sum=: +/) i.5에서 구 +/이 정의한 동사는 사용되기 전에 이름이 할당돼요. 그러나 문장 +/ i.5에서는 익명으로 사용돼요. 위 factorial 정의에서는, 정의 안에서 그것을 참조할 수 있게 하기 위해 이름을 할당하는 것이 필수적이었어요. 그러나 단어 $:은 익명 재귀 정의를 허용하는 자기 참조(self-reference)를 제공해요. 예를 들어:
1:`(]*$:@<:) @. * "0 i. 6
1 1 2 6 24 120
하노이 탑(Tower of Hanoi) 퍼즐에서, 서로 다른 크기의 n개 디스크 집합을 기둥 A에서 기둥 B로, 세 번째 기둥 C를 사용해, 더 큰 디스크가 더 작은 디스크 위에 절대 놓이지 않는다는 제약 아래 옮겨야 해요. 다음은 그 과정의 재귀 정의예요:
h=: b`(p,.q,.r)@.c
c=: 1: < [
b=: 2&,@[ $ ]
p=: <:@[ h 1: A. ]
q=: 1: h ]
r=: <:@[ h 5: A. ]
3 h x=: 'ABC'
AABACCA
BCCBABB
0 1 2 3 4 <@h"0 1 x
++-+---+-------+---------------+
||A|AAC|AABACCA|AACABBAACCBCAAC|
||B|CBB|BCCBABB|CBBCACCBBAABCBB|
++-+---+-------+---------------+
연습문제 (Exercises)
22.1
이것들을 읽고 쓰기의 연습으로 사용해 보세요:
f=:1:`(+//.@(,:~)@($:@<:))@.* Binomial Coeffs
<@f"0 i.6 Boxed binomials
g=:1:`((],+/@(_2&{.))@$:@<:)@.* Fibonacci