재귀 함수와 분할 정복, 문제를 쪼개는 원리와 비용 계산
재귀 함수는 자기 자신을 호출해 문제를 풀고, 분할 정복은 문제를 잘게 쪼갠 뒤 합쳐 푸는 전략이다. 두 개념의 관계와 병합 정렬·이진 탐색의 점화식, 마스터 정리로 성능을 계산하는 법, 파이썬 재귀 한계까지 짚는다.
재귀 함수와 분할 정복의 관계
재귀 함수(recursive function)는 함수가 실행 도중 자기 자신을 다시 호출해 문제를 푸는 방식이다. 분할 정복(divide and conquer)은 하나의 큰 문제를 같은 형태의 더 작은 문제 여러 개로 나눠 각각 풀고, 그 답을 합쳐 원래 문제의 답을 만드는 설계 전략이다. 재귀는 구현 수단이고, 분할 정복은 문제를 바라보는 전략이다.
둘은 자주 함께 등장하지만 같은 말은 아니다. 대부분의 분할 정복 알고리즘은 재귀로 구현되지만, 모든 재귀가 분할 정복은 아니다. 팩토리얼을 구하는 재귀는 문제를 반으로 쪼개지 않고 크기를 1씩만 줄이므로 분할 정복이라 부르지 않는다. 반대로 분할 정복의 핵심인 절반으로 쪼개기는 재귀 없이 반복문으로도 짤 수 있다.
이 글은 특정 언어나 프레임워크에 매이지 않은 개념·설계 관점의 정리다. 코드는 이해를 돕기 위해 파이썬으로 들지만 요지는 언어와 무관하고, 자료구조·알고리즘 입문을 한 번 지난 개발자가 두 개념의 관계와 성능 계산법을 다시 잡는 데 초점을 둔다.
재귀 함수는 어떻게 동작하나
재귀 함수는 두 부분으로 이뤄진다. 더 이상 쪼갤 수 없는 최소 문제를 직접 답하는 기저 조건(base case)과, 자신을 더 작은 입력으로 호출하는 재귀 조건(recursive case)이다. 기저 조건이 없거나 잘못 잡히면 호출이 끝나지 않고 무한히 이어진다.
재귀가 도는 동안 컴퓨터는 호출 스택(call stack)에 각 호출의 상태를 쌓는다. 함수가 자신을 부를 때마다 지역 변수와 돌아갈 위치가 스택 프레임 하나로 쌓이고, 기저 조건에 닿으면 쌓인 프레임이 역순으로 하나씩 풀리며 결과가 위로 전달된다. 스택 프레임이 인자와 돌아갈 주소를 어떤 규칙으로 배치하는지는 호출 규약(calling convention)이 정하는데, 이 규약을 기계어 수준에서 직접 읽는 방법은 x86 어셈블리 리버싱 입문에서 다룬다. 재귀 깊이가 곧 스택에 쌓이는 프레임 수라는 점이 나중에 성능과 안정성의 갈림길이 된다.
def factorial(n):
if n <= 1: # 기저 조건: 더 나눌 수 없는 최소 문제
return 1
return n * factorial(n - 1) # 재귀 조건: 더 작은 문제로 위임
이 코드에서 factorial(5)는 factorial(4)를, 그것은 다시 factorial(3)을 부르며 내려가다가 n이 1이 되는 순간 멈춘다. 기저 조건 한 줄을 빼면 n이 0 아래로 계속 내려가 무한 재귀에 빠지므로, 재귀를 짤 때는 어디서 멈출지부터 정하는 편이 안전하다.
분할 정복의 세 단계: 나누고 풀고 합친다
분할 정복은 세 단계로 움직인다. 문제를 더 작은 부분 문제로 나누고(divide), 각 부분을 재귀로 풀고(conquer), 부분의 답을 합쳐 전체 답을 만든다(combine). 세 단계 중 어디에 비용이 쏠리는지가 알고리즘의 성능을 결정한다.
병합 정렬(merge sort)이 교과서적인 예다. 배열을 절반으로 계속 나눠 원소가 하나만 남으면 그 자체로 정렬된 상태로 보고(정복), 정렬된 두 조각을 앞에서부터 비교하며 하나로 합친다(합치기). 나누는 데는 거의 비용이 안 들지만 합치는 데 매 단계 전체 크기만큼의 비교가 든다. 이진 탐색(binary search)은 더 단순하다. 정렬된 배열의 가운데 값과 목표를 비교해 한쪽 절반을 통째로 버리고 남은 절반만 다시 탐색한다.
def binary_search(arr, target, lo, hi):
if lo > hi: # 기저 조건: 구간이 비면 못 찾음
return -1
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
if arr[mid] < target: # 목표가 더 크면 오른쪽 절반만
return binary_search(arr, target, mid + 1, hi)
return binary_search(arr, target, lo, mid - 1) # 아니면 왼쪽 절반
이진 탐색은 매 호출에서 탐색 범위를 반으로 줄인다. 원소가 100만 개라도 절반씩 버리면 스무 번 남짓이면 바닥에 닿는다. 매번 절반씩 줄인다는 이 감각이 분할 정복 성능 분석의 출발점이다.
성능은 어떻게 계산하나
분할 정복의 실행 시간은 점화식(recurrence)으로 적고, 마스터 정리(master theorem)로 닫힌 형태를 얻는다. 점화식은 전체 문제 비용을 부분 문제 비용의 합과 나누고 합치는 비용으로 나눠 적은 식으로, 보통 T(n) = a·T(n/b) + f(n)로 쓴다. 여기서 a는 부분 문제의 개수, b는 문제 크기를 줄이는 비율, f(n)은 나누고 합치는 데 드는 비용이다.
마스터 정리는 log_b(a)와 f(n)의 증가율을 견줘 셋 중 한 경우로 결과를 정해 준다. 알고리즘 교과서 《Introduction to Algorithms》(흔히 CLRS로 부른다)가 이 정리를 표준 형태로 정리해 두었다. 병합 정렬에 대입하면 a=2, b=2, f(n)=Θ(n)이고 log₂2 = 1이라 f(n)의 증가율과 맞아떨어져 T(n) = O(n log n)이 나온다. 이진 탐색은 a=1, b=2, f(n)=O(1)이라 O(log n)이다.
| 알고리즘 | 점화식 | 시간 복잡도 |
|---|---|---|
| 이진 탐색 | T(n) = T(n/2) + O(1) | O(log n) |
| 병합 정렬 | T(n) = 2T(n/2) + O(n) | O(n log n) |
| 카라츠바 곱셈 | T(n) = 3T(n/2) + O(n) | 약 O(n^1.585) |
같은 절반 나누기라도 부분 문제를 몇 개 만드느냐에 따라 결과가 갈린다. 카라츠바 곱셈은 큰 수 두 개를 곱할 때 부분 곱을 4번에서 3번으로 줄여 T(n) = 3T(n/2) + O(n)이 되고, 이는 약 O(n^1.585)로 자릿수마다 곱하는 방식의 O(n²)보다 빠르다. 한편 퀵 정렬(quicksort)은 분할 정복이지만 나누는 기준값이 한쪽으로 치우쳐 균형이 무너지면, 평균은 O(n log n)이어도 최악에는 O(n²)까지 느려진다. 점화식이 성능을 결정한다는 사실이 여기서도 드러난다.
재귀의 한계: 스택 오버플로와 꼬리 호출
재귀는 깔끔하지만 공짜가 아니다. 호출마다 스택 프레임이 쌓이므로 재귀가 너무 깊어지면 스택이 넘쳐 프로그램이 죽는다. 파이썬 공식 문서의 sys 모듈 설명에 따르면 기본 재귀 한계는 1000이며, sys.setrecursionlimit()으로 조정할 수 있다. 다만 한계를 무작정 올리면 C 스택이 먼저 터질 수 있어 근본 해법은 아니다.
일부 언어는 꼬리 호출 최적화(tail call optimization)로 이 문제를 피한다. 재귀 호출이 함수의 맨 마지막 동작이면 현재 프레임을 재사용해 스택을 늘리지 않는 기법인데, CPython은 이 최적화를 하지 않는다. 그래서 파이썬에서 아주 깊은 재귀가 필요하면 반복문이나 명시적 스택(리스트)으로 바꾸는 편이 안전하다.
실무 기준은 단순하다. 문제가 자연스럽게 자기 닮은 부분 문제로 쪼개지고 깊이가 얕으면(트리 순회, 정렬, 파서 등) 재귀가 읽기 쉽다. 반대로 깊이가 입력 크기에 비례해 수만 단계로 늘어날 수 있으면 반복으로 바꾸거나 깊이를 로그 수준으로 눌러야 한다. 분할 정복이 매번 절반으로 줄여 깊이가 log n에 그치는 것도 이 안정성 덕을 본다.
