5.2.3 점화식

상태와 종료 조건을 정의한 후에는 가장 큰 상태가 어떤 과정을 거쳐 가장 작은 상태인 종료 조건에 도달하는지 정의해야 합니다. 부분 문제는 같은 규칙으로 더 작은 부분 문제로 진행되어야 합니다. 따라서 상태 또한 하나의 규칙으로 더 작은 상태로 전이되어야 합니다. 이렇게 상태를 전이시키는 규칙을 점화식이라고 합니다.

예시 문제에서는 n^m = n × n^m-1의 식을 세울 수 있습니다. 이를 상태로 변환하면 다음과 같이 점화식을 표기할 수 있습니다.

(n, m) = n × (n, m – 1)

이 식을 살펴보면, 상태가 전이될수록 m 값은 점점 줄어들며 결국에는 0에 도달할 것입니다. m 값이 0에 도달하면 앞서 세운 종료 조건에 따라 재귀가 종료됩니다.