러시아 인형(마트료시카)을 열면 같은 모양의 더 작은 인형이 나오듯, 재귀는 문제 안에서 더 작은 같은 문제를 풀어 답을 만든다. 함수가 자기 자신을 부르고, 가장 작은 경우에서 멈춘다. 백트래킹은 재귀로 선택을 하나씩 쌓아 가다가, 막히면 마지막 선택을 되돌리고 다른 길로 가는 방법이다. 짧고 자연스럽게 쓸 수 있지만, 멈추는 조건을 빼먹으면 끝나지 않고, 파이썬은 깊이가 1,000쯤 넘으면 오류가 난다.
예시로 보기
재귀: 1부터 n까지의 합
“1부터 n까지의 합 = (1부터 n − 1까지의 합) + n”이다. 같은 모양의 더 작은 문제가 안에 들어 있다.
def total(n):
if n == 0: # 가장 작은 경우: 멈춘다 (기저 사례)
return 0
return total(n - 1) + n # 더 작은 문제로 (재귀 사례)
total(3)을 부르면 이렇게 쌓였다가 거꾸로 풀린다.
| 단계 | 일 | 쌓인 호출 (오른쪽이 맨 위) |
|---|---|---|
| 1 | total(3)이 total(2)를 부른다 | total(3) |
| 2 | total(2)가 total(1)을 부른다 | total(3) total(2) |
| 3 | total(1)이 total(0)을 부른다 | total(3) total(2) total(1) |
| 4 | total(0)이 0을 돌려준다 | total(3) total(2) total(1) total(0) |
| 5 | total(1) = 0 + 1 = 1 | total(3) total(2) total(1) |
| 6 | total(2) = 1 + 2 = 3 | total(3) total(2) |
| 7 | total(3) = 3 + 3 = 6 | total(3) |
아직 끝나지 않은 호출들은 스택처럼 쌓인다(호출 스택). 맨 위부터 끝나며 돌아온다.
백트래킹: 1, 2, 3으로 두 자리 순서 만들기
자리를 하나씩 채운다. 이미 쓴 수는 다시 쓰지 않는다.
시작 []
├─ [1] ─┬─ [1,2] 완성
│ └─ [1,3] 완성
├─ [2] ─┬─ [2,1] 완성
│ └─ [2,3] 완성
└─ [3] ─┬─ [3,1] 완성
└─ [3,2] 완성
[1, 2]를 완성한 뒤에는 2를 빼고(되돌리기) [1, 3]으로 간다. 1 아래를 다 보면 1도 빼고 [2]로 간다. 이렇게 “넣고 → 더 들어가고 → 빼기”를 되풀이하며 나무 전체를 돈다.
재귀를 짜는 법
- 기저 사례: 더 쪼갤 필요 없이 바로 답이 나오는 가장 작은 경우. 반드시 먼저 검사한다.
- 재귀 사례: 지금 문제를 더 작은 같은 문제로 바꾸고, 그 답으로 지금 답을 만든다. 부를 때마다 문제가 기저 사례 쪽으로 반드시 작아져야 한다.
- 믿기: 더 작은 문제의 답은 맞게 돌아온다고 믿고 지금 단계만 짠다.
입력 크기가 음이 아닌 정수 n일 때, (1) 기저 사례에서 답이 맞고, (2) n보다 작은 모든 입력에서 맞다고 가정하면 n에서도 맞으며, (3) 재귀 호출마다 크기가 줄어든다면, 그 함수는 모든 n에서 끝나고 맞는 답을 낸다.
증명
강한 귀납법이다. n = 0(기저)에서 (1)로 맞다. n보다 작은 모든 크기에서 끝나고 맞는다고 하자. 크기 n에서 함수는 (3)에 따라 더 작은 크기만 부르므로 그 호출들은 가정에 따라 끝나고 맞는 값을 돌려준다. 그러면 (2)에 따라 크기 n의 결과도 맞다. ∎
백트래킹 틀
def backtrack(chosen):
if 다 골랐다(chosen):
결과에 기록(chosen[:]) # 복사해서 기록한다
return
for c in 고를_수_있는_것(chosen):
if 이미_틀렸다(chosen, c): # 가지치기: 더 들어가 봐야 소용없다
continue
chosen.append(c) # 고른다
backtrack(chosen) # 더 들어간다
chosen.pop() # 되돌린다
chosen[:]로 복사해서 기록한다.chosen은 계속 넣고 빼는 같은 리스트라서, 그대로 기록하면 나중에 비어 버린다.- 가지치기: 더 들어가도 답이 될 수 없으면 그 아래 나무 전체를 건너뛴다. 예를 들어 합이 목표를 넘으면 더 더하지 않는다(모두 양수일 때). 가지치기는 완전탐색보다 빨라지게 하는 유일한 장치다2.
스스로 설명해 보기
양수들 중 몇 개를 골라 합이 target이 되는 경우를 세는 코드다. 줄마다 왜 있는지 답해 본다.
def count_subsets(nums, target):
nums = sorted(nums) # (1)
def go(start, remain):
if remain == 0: # (2)
return 1
cnt = 0
for i in range(start, len(nums)): # (3)
if nums[i] > remain: # (4)
break
cnt += go(i + 1, remain - nums[i]) # (5)
return cnt
return go(0, target)
1. (5)에서 i + 1부터 다시 보는 까닭은?
같은 수를 두 번 쓰지 않고, 같은 조합을 순서만 바꿔 여러 번 세지 않으려고 한다. 항상 앞에서 고른 것보다 뒤의 수만 고르면 조합마다 한 가지 순서로만 만들어진다.
2. (4)에서 continue가 아니라 break를 써도 되는 까닭은?
(1)에서 정렬했기 때문이다. nums[i]가 남은 합보다 크면 그 뒤의 수는 더 크니 모두 넘친다. 한 번에 뒤를 다 버려도 된다. 이것이 가지치기다.
3. (2)가 반복문보다 앞에 있어야 하는 까닭은?
남은 합이 0이면 이미 한 경우가 완성되었다. 여기서 1을 돌려주고 멈춘다. 멈추는 조건(기저 사례)을 먼저 보고, 아닐 때만 더 들어가는 것이 재귀를 짜는 기본 순서다. 순서를 바꾸면 완성된 경우에서도 쓸데없이 더 들어가거나, 조건을 빼먹기 쉽다.
이 코드의 핵심 아이디어는?
“앞에서부터 하나씩 고르되, 고른 것보다 뒤만 본다”로 조합을 겹침 없이 만들고, 정렬을 이용해 넘치는 가지를 통째로 버린다.
같은 방법을 쓸 수 있는 다른 상황은?
순서를 세우는 문제(순열), 격자에서 길 찾기, N-Queen, 스도쿠처럼 “선택을 쌓다가 규칙을 어기면 되돌리는” 모든 문제다.
RecursionError가 나는 것을 확인했다. 예제 사다리의 답(조합 수, N-Queen 해 개수 1·0·0·2·10·4·40·92, 괄호 개수)도 확인했다 — 17_recursion-backtracking_verify.py예제
더 많은 연습은 재귀와 백트래킹 예제 사다리에 있다.
- 경계: 기저 사례가 입력의 가장 작은 값(0, 빈 리스트)을 모두 덮는지 본다.
total(-1)처럼 기저보다 작은 값이 들어오면 끝나지 않는다. - 가정이 깨지는 예: 스스로 설명해 보기의
break는 “모두 양수이고 정렬됨”이 전제다. 음수가 있으면 “지금 수가 남은 합보다 크면 뒤의 수도 모두 넘친다”가 깨진다. 예: nums = [−3, −2], target = −5. 처음부터 −3 > −5라break되어 0개로 세지만, −3 + (−2) = −5라 답은 1개다.
활용
- 자연스럽게 재귀인 것: 트리·그래프 탐색, 분할 정복(병합 정렬), 괄호처럼 안에 같은 모양이 들어 있는 문자열.
- 백트래킹이 쓰이는 곳: 순열·조합 나열, 퍼즐(스도쿠, N-Queen), 조건을 만족하는 배치 찾기.
- 파이썬의 한계: 재귀 깊이 기본 한도는 1,000이다(
sys.getrecursionlimit()). 더 깊으면RecursionError가 난다.sys.setrecursionlimit(10**6)으로 늘릴 수 있지만, 아주 깊으면 프로그램이 통째로 죽을 수 있다. 깊이가 수만 이상이면 반복문과 스택으로 바꾼다3. - 같은 작은 문제를 여러 번 푸는 재귀(예: 피보나치)는 답을 적어 두면 빨라진다. 이것이 동적 계획법이다.
연결
- 선수: 완전탐색, 스택, 재귀적 정의와 구조적 귀납법
- 맞다는 근거: 수학적 귀납법
- 부분집합을 반복문으로 돌 때는 비트마스크도 쓴다.
- 피보나치를 정의 그대로 재귀하면 n이 1 늘 때마다 호출 수가 약 1.618배로 는다. 정확한 호출 수와 1.618이 나오는 까닭은 선형 점화식에 있다.
- 예시로 보기의 두 자리 순서 나무는 첫 층에서 3갈래, 둘째 층에서는 어느 마디든 2갈래라 잎이 3 × 2 = 6개다. 층마다 갈래 수가 앞의 선택과 상관없이 같으면 잎 수를 일반화된 곱의 법칙으로 미리 센다. 가지치기를 하면 갈래 수가 앞의 선택에 따라 달라지므로, 대개 곱 하나로는 미리 셀 수 없다.
- 스스로 설명해 보기의
count_subsets가 세는 값은 생성함수 \((1 + x^{a_1})(1 + x^{a_2})\cdots(1 + x^{a_n})\)에서 \(x^{\text{target}}\)의 계수다. 여기서 \(a_i\)는 nums의 \(i\)번째 수다. 괄호마다 1은 그 수를 건너뛰기, \(x^{a_i}\)는 고르기다. 백트래킹은 이 곱을 항 하나씩 펼쳐 세는 일이고, (4)의break는 지수가 target을 넘는 항을 버리는 일이다. - 연습: 괄호 변환, 양궁대회, 불량 사용자, 양과 늑대, 4단 고음
자주 하는 오해
틀렸다. 파이썬에서 리스트를 함수에 넘기면 복사본이 아니라 같은 리스트를 가리킨다. 호출마다 따로 있는 것처럼 보이는 이유는 함수 안의 이름(chosen)이 호출마다 새로 생기기 때문이다. 하지만 그 이름들은 모두 한 리스트를 가리킨다. 그래서 append한 것을 pop으로 되돌리지 않으면 다른 가지에 앞 가지의 선택이 남는다. 결과를 기록할 때도 chosen[:]로 복사하지 않으면, 나중의 넣고 빼기가 기록된 결과까지 바꾼다. 확인하려면 되돌리기를 뺀 코드로 1, 2, 3의 순서를 만들어 보면 된다. 첫 결과 뒤로는 길이가 계속 늘어나 틀린 결과가 나온다.
과목별 관점
컴파일러 (3-2학기). 문법대로 입력을 읽는 가장 단순한 방법인 재귀 하강 파싱이 백트래킹이다. 문법의 이름 하나를 풀어 쓸 규칙이 여럿이면 적힌 순서대로 하나를 골라 들어가 보고, 입력과 어긋나면 되돌아가 다음 규칙을 고른다. 위의 틀과 짝지으면 다음과 같다4.
| 백트래킹 틀 | 재귀 하강 파싱 |
|---|---|
| 고를 수 있는 것 | 지금 풀어야 할 이름의 규칙들 |
고른다(append) |
규칙 하나를 골라 그 조각들로 바꾼다 |
| 더 들어간다 | 조각 안의 이름마다 다시 같은 함수를 부른다 |
| 이미 틀렸다 | 규칙이 내놓은 낱말이 입력의 다음 낱말과 다르다 |
되돌린다(pop) |
입력을 읽던 자리를 갈림길 위치로 돌려놓는다 |
| 다 골랐다 | 풀 이름이 남지 않고 입력도 끝났다 |
- 되돌릴 것이 하나 더 있다. 위 오해 항목처럼 고른 것을 물리지 않으면 다른 가지가 망가진다. 파서에서는 물릴 것이 “입력을 어디까지 읽었는가”다. 예를 들어 규칙 \(S \to cAe\)가 입력 \(cad\)의 \(c\), \(a\)까지 맞추고 \(e\)에서 틀리면, 읽던 자리를 맨 앞으로 돌린 뒤 \(S \to cAd\)를 시험한다.
- “반드시 작아져야 한다”가 깨지는 문법. 규칙 \(S \to Sa\)처럼 오른쪽 맨 앞에 자기 자신이 오면, 입력을 한 낱말도 읽지 않은 채 같은 자리에서 같은 함수를 다시 부른다. 문제가 작아지지 않으니 위 정리의 조건 (3)이 깨지고 끝나지 않는다. 그래서 재귀 하강 파싱을 쓰려면 이런 규칙(좌재귀)이 없어야 한다. 고치는 법은 좌재귀 없애기에 있다.
- 가지치기를 끝까지 밀면 되돌아가기가 없어진다. 재귀 하강이 잘 쓰이지 않는 까닭이 이 되돌아가기다. 산술식 문법으로 괄호를 겹친 식을 읽으면 시험한 규칙 수가 괄호 0겹에서 14, 1겹에서 69, 2겹에서 292로 한 겹마다 4배 넘게 는다. 규칙을 고르기 전에 입력의 다음 낱말 하나를 보고 “이 규칙은 그 낱말로 시작할 수 없다”를 미리 알면 그 가지에 아예 들어가지 않는다. 문법을 다듬어 남는 가지가 늘 하나가 되게 한 것이 LL(1) 파싱 표이고, 같은 입력에서 8, 15, 22로 한 겹마다 7씩만 는다4.
확인 문제
C1 def f(n): return 1 if n <= 1 else f(n - 1) + f(n - 2)에서 f(4)의 값과, f가 불리는 총 횟수는?
답: 값은 5, 호출은 9번이다. f(4) → f(3), f(2) / f(3) → f(2), f(1) / f(2) → f(1), f(0)이다. 그래서 f(4) 1번, f(3) 1번, f(2) 2번, f(1) 3번, f(0) 2번으로 9번이다. f(2)를 두 번 계산하는 낭비가 보인다.
C2 백트래킹 틀에서 chosen.pop()을 빼먹으면 무슨 일이 생기는가?
답: 한 가지를 다 본 뒤에도 그 선택이 리스트에 남는다. 다음 후보를 넣을 때 앞 선택 위에 쌓여서 길이가 계속 늘고, 다른 가지의 결과가 틀린다. 넣은 것을 빼야 “그 선택을 하지 않은 상태”로 돌아가 다음 후보를 시험할 수 있다.
C3 total(n)이 모든 n ≥ 0에서 1 + … + n을 돌려준다는 것을 무엇으로 보이는가? 각 단계를 말하라.
답: 수학적 귀납법이다. n = 0이면 0을 돌려주니 맞다(기저). total(n − 1)이 1 + … + (n − 1)을 돌려준다고 가정하면, total(n) = total(n − 1) + n = 1 + … + n이다. 호출마다 n이 1씩 줄어 0에서 멈추니 끝난다.
C4 “정렬한 뒤 남은 합보다 큰 수가 나오면 break“라는 가지치기가 답을 빠뜨리는 입력을 하나 만들어라.
답: nums = [−3, −2], target = −5. 정렬해도 [−3, −2]이고, 처음부터 −3 > −5라 break되어 0개로 센다. 하지만 −3 + (−2) = −5라 답은 1개다. 음수를 더하면 합이 작아지므로 “지금 수가 남은 합보다 크면 뒤도 모두 넘친다”는 가정이 깨진다. 이 가지치기는 모든 수가 양수일 때만 쓴다.
C5 문법대로 입력을 읽는 재귀 하강 파싱을 백트래킹 틀의 “고른다, 더 들어간다, 되돌린다”로 옮겨라. 규칙 \(S \to Sa \mid b\)에서는 왜 끝나지 않는가?
답: 고른다: 풀어야 할 이름의 규칙 하나를 적힌 순서대로 고른다. 더 들어간다: 그 규칙의 조각들을 왼쪽부터 맞추고, 조각이 이름이면 같은 함수를 다시 부른다. 되돌린다: 입력과 어긋나면 읽던 자리를 이 이름을 풀기 시작한 곳으로 돌리고 다음 규칙을 고른다. \(S \to Sa\)를 고르면 첫 조각이 다시 \(S\)라서, 입력을 하나도 읽지 않은 채 같은 자리에서 같은 함수를 부른다.
이유: 재귀는 부를 때마다 문제가 작아져야 끝난다. 여기서 문제의 크기는 남은 입력인데, 좌재귀는 남은 입력을 줄이지 않는다.
-
재귀와 귀납법의 대응은 재귀적 정의와 구조적 귀납법과 수학적 귀납법 문서를 따른다. 정리는 그 내용을 재귀 함수에 맞게 옮겨 쓴 것이다. ↩
-
Laaksonen, Competitive Programmer’s Handbook (2018년 7월판), 5.3 “Backtracking”, 5.4 “Pruning the search”. ↩
-
Python 3 표준 라이브러리 문서,
sys.getrecursionlimit,sys.setrecursionlimit: 한도를 너무 높이면 인터프리터가 멈출(crash) 수 있다고 경고한다. 기본값 1,000은 이 컴퓨터(Python 3.14)에서 확인했다. ↩ -
규칙 수는 17_recursive-descent-parsing_impl.py를 돌려 얻었고, 좌재귀 문법에서
RecursionError가 나는 것도 같은 코드로 확인했다. ↩ ↩2