주어진 함수를 정의하면
A(x, y) = { 0 만일 y가 0이면
2 * y 만일 x가 0이면
2 만일 y가 1이면
A(x - 1, A(x, y -1))); 그밖의 경우
}
따라서 A(1,10)는
A(1, 10)
A(0, A(1, 9))
2 * A(1, 9)
2 * A(0, A(1,8))
.....
2^10
A(2,4)는
A(2, 4)
A(1, A(2,3))
A(1, A(1, A(2, 2))))
A(1, A(1, A(1, A(2, 1)))))
A(1, A(1, A(1, 2))))
A(1, A(1, A(0, A(1, 1))))
A(1, A(1, A(0, 2))))
A(1, A(1, 4)))
A(2, 4) -> A(1, A(1, 4)) -> A(1, 16)
2^16
A(3,3)는
A(3, 3)
A(2, A(2,2))
A(2, 4)
따라서 f(n) = 2n, g(n) = 2^n, h(n) = 2^2^2..(n번)
728x90