점화식 (Recurrence Relation)

한 줄 정의: 수열의 각 항을 그보다 앞선 항들을 이용해 정의하는 식입니다.

쉽게 풀면

도미노가 쓰러지는 모습을 떠올려보세요. 지금 도미노가 쓰러질지 안 쓰러질지는 바로 앞 도미노가 쓰러졌는지만 알면 결정할 수 있습니다. 점화식도 마찬가지입니다. "n번째 항은 (n-1)번째 항에 2를 곱한 값이다"처럼, 바로 앞의 항(들)을 알면 다음 항을 계산할 수 있는 규칙을 식으로 적어 놓은 것이 점화식입니다. 대표적인 예로 피보나치 수열은 "앞의 두 항을 더하면 다음 항이 된다"는 점화식으로 정의됩니다.

왜 중요한가

점화식은 재귀적으로 정의되는 대상의 성질을 다루기 위한 가장 기본적인 도구이기 때문에, 알고리즘의 시간복잡도 분석, 조합론적 대상의 개수 세기, 동적계획법 설계 등 여러 연구 주제에서 공통으로 등장합니다. 어떤 문제를 더 작은 크기의 같은 문제로 쪼갤 수 있다는 사실을 점화식으로 표현하고 나면, 이를 풀거나 근사해서 전체 문제의 답이나 성능을 유도할 수 있기 때문에 이론 논문에서 특히 자주 다뤄집니다.

논문에서는 이렇게 쓰입니다

"재귀적으로 구현된 정렬 알고리즘의 실행 시간을 T(n) = 2T(n/2) + O(n)이라는 점화식으로 나타내고, 이를 풀어 시간복잡도가 O(n log n)임을 보였다."

이 문장은 알고리즘이 자기 자신을 더 작은 크기로 호출하는 구조를 가질 때, 그 실행 시간을 점화식으로 표현한 다음 이를 풀어서 전체 실행 시간을 구했다는 뜻입니다. 이렇게 알고리즘의 복잡도를 점화식으로 세우고 분석하는 방법은 재귀 알고리즘의 효율성을 증명하는 논문에서 흔히 쓰입니다.

"n번째 항이 이전 두 항의 합으로 정의되는 점화식을 이용해 개체군의 세대별 증식 패턴을 모형화하였다."

생태학이나 개체군 동태 연구에서는 세대를 거듭할 때 개체 수가 어떻게 변하는지를 점화식으로 표현해, 장기적인 증가 추세나 안정 상태를 예측하는 데 활용합니다.

"동적계획법에서는 부분 문제 사이의 관계를 점화식으로 정의한 뒤, 이를 상향식으로 계산하여 중복 계산을 제거하였다."

동적계획법 논문에서는 문제를 점화식으로 정식화하는 것이 알고리즘 설계의 출발점이며, 이 점화식을 어떻게 효율적으로 계산하느냐가 곧 알고리즘의 성능을 좌우합니다.

조금 더 깊게 보면

점화식을 실제로 "푼다"는 것은 n번째 항을 이전 항들이 아니라 n에 대한 닫힌 형태의 식(폐쇄형 해)으로 바꾸는 작업을 뜻합니다. 특성방정식을 이용하는 방법, 생성함수를 이용하는 방법, 마스터 정리처럼 알고리즘 분석에 특화된 정리를 이용하는 방법 등이 대표적입니다. 점화식이 복잡해 정확한 해를 구하기 어려운 경우에는 점근적 증가율(예: O 표기법)만 구해도 충분한 경우가 많으며, 이 때문에 알고리즘 논문에서는 점화식을 엄밀히 풀기보다 점근적 상한을 유도하는 데 그치는 경우도 흔합니다.

주의할 점

등차수열과 등비수열은 각각 "이전 항에 일정한 수를 더한다", "이전 항에 일정한 수를 곱한다"는 규칙을 가진 점화식의 특수한 사례일 뿐이며, 점화식은 훨씬 다양하고 복잡한 규칙(예: 이전 두 항을 모두 사용하는 경우)까지 포괄하는 더 일반적인 개념입니다.