이중재귀
Double recursion재귀함수 이론에서 이중재귀는 원시 재귀의 연장선으로, 아커만 함수와 같은 비원초적 재귀함수의 정의를 가능하게 한다.
Raphael M. Robinson은 주어진 함수에 대해 두 개의 자연수 변수 G(n, x)의 함수를 이중재귀라고 불렀다.
- G(0, x)는 x의 주어진 함수다.
- G(n + 1, 0)는 함수 G(n, ·)와 주어진 함수에서 대체하여 구한다.
- G(n + 1, x + 1)는 G(n + 1, x), 함수 G(n, ·) 및 주어진 함수에서 대체하여 구한다.[1]
로빈슨은 계속해서 특정한 이중 재귀 기능을 제공한다(원래 로자 페터가 정의함).
- G(0, x) = x + 1
- G(n + 1, 0) = G(n, 1)
- G(n + 1, x + 1) = G(n, G(n + 1, x)
여기서 주어진 함수는 원시 재귀이지만 G는 원시 재귀가 아니다.사실, 이것은 정확히 현재 아커만 함수로 알려진 기능이다.
참고 항목
참조
- ^ Raphael M. Robinson (1948). "Recursion and Double Recursion". Bulletin of the American Mathematical Society. 54: 987–93. doi:10.1090/S0002-9904-1948-09121-2.
