5.2.2 종료 조건

재귀는 하나의 문제를 부분 문제들로 나누거나 부분 문제의 답을 이용하여 원본 문제의 답을 찾아야 풀 수 있습니다. 그리고 이렇게 부분 문제들을 생성해 나가다 보면 언젠가는 종료해야 합니다. 부분 문제는 상태에 대한 답을 찾는 것이므로 부분 문제가 나타내는 상태는 재귀가 진행될수록 점점 작아져, 결국 이어지는 부분 문제 없이 즉시 답이 나와야 합니다.

이렇게 즉시 답이 나오는 상태를 검사하여 답을 반환할 수 있도록 하는 것을 종료 조건이라고 하고, 종료 조건에 도달할 수 있도록 부분 문제로 상태가 변해 가는 것을 상태가 작아진다고 합니다.

예시 문제에서는 가장 작은 상태는 계산할 필요 없이 상태만으로 답이 즉시 정해지는 다음 세 가지 상황입니다.

1. n의 0제곱을 구할 때 (m=0) 답은 1

2. 0의 m제곱을 구할 때 (n=0) 답은 1

3. 1의 m제곱을 구할 때 (n=1) 답은 1

이 세 가지 상황은 계산할 필요 없이 즉시 1이라는 답을 낼 수 있습니다. 이 조건들은 다음과 같이 표기합니다.

• (n, 0) = 1

• (0, m) = 1

• (1, m) = 1

(n, 0) = 1의 상태를 예시로 조금 더 자세히 살펴보면 n 변수는 상태에 그대로 남아 있고, m의 자리에는 0이 들어 있습니다. 이는 n 값에 어떤 값이 오든 상관없고, m 값은 0이라는 의미입니다. 즉, n에 어떤 값이 들어오든 m 값이 0이라면 해당 부분 문제의 답은 1이 됩니다.