이 코드에서 알 수 있듯이, 상태 변수는 메서드의 입력부에 들어갑니다. 상태 정보를 입력받은 재귀 메서드는 해당 상태에 대한 부분 문제를 풀기 시작합니다. 예를 들어 2⁵을 나타내는 상태인 (2, 5)의 부분 문제를 푸는 메서드는 power(2, 5)가 됩니다.

종료 조건 작성하기

종료 조건은 조건을 만족할 경우 그 즉시 답을 낼 수 있습니다. 예시 문제의 종료 조건을 다음과 같이 구현합니다.

private int power(int n, int m) {
    if (m == 0) return 1;
    if (n == 1) return 1;
    if (n == 0) return 1;
    
    // 점화식 구현하기
}

점화식 구현하기

점화식은 하나의 부분 문제를 더 작은 상태를 나타내는 부분 문제를 이용하여 푸는 규칙입니다. 부분 문제를 푸는 메서드는 power()이므로, 이 메서드에 더 작은 상태를 넣어 주면 해당 상태를 풀 수 있습니다. 이를 이용하여 점화식은 다음과 같이 구현할 수 있습니다.