5.2.1 상태 정의하기
재귀는 부분 문제를 해결해 나가는 풀이 방법입니다. 부분 문제는 각각 하나의 명확한 문제를 나타내어 하나의 답을 낼 수 있어야 합니다. 답을 내는 데 입력되는 변수들이 필요하고, 이렇게 답을 결정하는 변수들을 상태라고 합니다. 그리고 부분 문제는 하나의 상태에 대한 답을 찾는 문제가 됩니다. 앞으로 소괄호를 사용하여 상태를 표기하겠습니다. 예를 들어 두 변수 x, y를 사용하여 정의되는 상태는 (x, y)로 표기합니다.
예시에서 제시된 문제는 두 정수 n, m에 대해 nm을 구하는 것입니다. 여기에서는 2개의 변수가 있으므로 상태는 (n, m)으로 정의할 수 있습니다.
잠깐만요
예시 문제에서 상태는 제시된 문제로 정의했습니다. 재귀 문제 대부분은 가장 큰 부분 문제가 제시된 문제 자체인 경우가 많기 때문에 이렇게 제시된 문제로 상태를 정의할 수 있습니다.
하지만 간혹 이 방식으로 상태를 정의해도 문제를 풀기 어려운 경우가 있습니다. 이때는 부분 문제가 제시된 문제를 그대로 나타내는 것이 아니라 부분 문제의 답을 이용하여 제시된 문제의 답을 유도할 수 있도록 상태를 정의해야 합니다.