2. 재귀는 돌아오는 순서까지 읽는다
해설글
작성 · 3분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
큰 문제를 같은 모양의 작은 문제로 줄이는 방법
하노이 탑에는 출발 기둥 A, 보조 기둥 B, 도착 기둥 C가 있다. 한 번에는 원판 하나만 옮길 수 있고, 각 기둥의 맨 위 원판만 움직일 수 있으며, 큰 원판을 작은 원판 위에 놓을 수 없다. 원하는 결과는 두 원판이 C에 크기순으로 쌓인 상태다.
재귀는 함수가 자기 자신을 호출해 같은 모양의 더 작은 문제를 푸는 방식이다. 원판 두 개 문제는 위의 한 개를 옮기는 문제, 큰 원판 하나를 옮기는 작업, 다시 작은 원판 하나를 옮기는 문제로 줄어든다. 더 줄일 필요 없이 답을 바로 낼 수 있는 조건을 기저조건이라고 한다.
함수를 호출하면 매 호출의 인수와 돌아올 코드 위치가 호출 스택에 쌓인다. 스택은 나중에 들어간 항목이 먼저 나오는 저장 방식이다. 따라서 첫 재귀 호출이 끝나야 그 아래에 멈춰 있던 바깥 호출의 다음 줄이 실행된다.
재귀를 쓰는 이유에서 막힌 지점
재귀 노트는 첫 줄부터 묻는다.
재귀를 왜 써야할까?
그리고 기저조건, 기저조건을 향하는 진행 방향, 재귀 호출이 정상 작동한다고 보는 가정을 규칙으로 적어 두었다. 하지만 “자기 자신을 호출한다”는 정의만으로는 코드가 어느 순서로 실행되는지 잘 보이지 않는다. 하노이 탑 구현은 이 문제를 가장 짧게 드러낸다.
저장소의 하노이 탑 코드는 다음 세 단계다.
함수 H(c, s, m, e)에서 c는 옮길 원판 수, s는 출발 기둥, m은 중간에 사용할 보조 기둥, e는 최종 도착 기둥이다. 재귀 호출마다 네 인수의 값이 달라지므로, 같은 H를 부르더라도 그 호출이 맡은 출발·보조·도착 역할은 다를 수 있다.
H(c - 1, s, e, m);
printf("%c %c\n", s, e);
H(c - 1, m, s, e);
원판 c개를 옮기려면 위의 c-1개를 보조 기둥으로 옮기고, 가장 큰 원판을 목적지로 옮긴 뒤, 보조 기둥의 c-1개를 다시 목적지로 옮긴다. 가운데 printf는 두 호출이 모두 끝난 뒤 실행되는 것이 아니다. 첫 호출이 끝나 돌아온 순간 실행되고, 그 뒤 두 번째 호출로 들어간다.
원판 두 개를 한 줄씩 펼치기
H(2, A, B, C)를 호출하면 첫 문장은 H(1, A, C, B)다. 기저조건에 도착했으므로 A B를 출력하고 돌아온다. 이제 멈춰 있던 가운데 문장이 A C를 출력한다. 마지막으로 H(1, B, A, C)가 B C를 출력한다.
H(2, A, B, C)
├─ H(1, A, C, B) → A B
├─ 현재 호출 처리 → A C
└─ H(1, B, A, C) → B C
호출마다 c, s, m, e가 따로 보관된다. 첫 호출에서 돌아와도 바깥 호출의 인수와 다음 실행 위치가 남아 있는 이유가 호출 스택이다. “돌아오는 비용”은 이 상태를 다시 꺼내 실행을 잇는 과정에서 생긴다.
이번에 만든 하노이 호출 확인 코드로 원판 수에 따른 이동 횟수를 확인했다.
n=0 moves=0
n=1 moves=1
n=2 moves=3
n=3 moves=7
n=4 moves=15
여기서 센 값은 함수 호출 횟수가 아니라 원판을 실제로 옮기는 횟수다. 이동 횟수의 점화식은 $M(n)=2M(n-1)+1$이고, 결과는 $2^n-1$이다. 함수 진입 자체를 세면 기저 호출까지 포함되어 다른 수가 된다. 입력이 하나 늘 때 핵심 작업인 이동이 거의 두 배가 된다는 결론은 같다. 재귀 코드가 짧다는 사실과 실행량이 작다는 사실은 다르다.
기저조건은 입력 범위까지 말해야 한다
저장소 원본은 c == 1일 때만 종료한다. 과제 입력이 양의 정수만 준다면 충분하다. 그러나 c=0을 허용하면 H(-1), H(-2)로 멀어져 종료하지 않는다. 원래 문제 명세를 확보하지 않은 상태에서 이를 과제의 실패라고 단정할 수는 없다.
현재의 범용 예제는 n <= 0에서 돌아오도록 만들었다.
if (n <= 0) return;
이 차이는 기저조건을 외워 쓰기보다 함수가 받을 수 있는 입력 범위를 함께 정해야 한다는 뜻이다.
노트에는 “꼬리재귀를 쓰면 함수가 복귀하지 않는다”는 설명도 남아 있다. 정확히는 꼬리재귀도 언어 의미상 호출에서 복귀한다. 다만 재귀 호출 뒤에 할 일이 없으면 컴파일러가 현재 호출 프레임을 재사용하도록 최적화할 수 있다. C가 그 최적화를 보장하지는 않으며, 하노이 탑은 첫 호출 뒤 출력과 두 번째 호출이 남아 있어 꼬리재귀도 아니다.
재귀를 읽을 때는 이제 세 가지를 적는다. 어디에서 멈추는가, 다음 호출의 인수가 기저조건으로 가까워지는가, 호출에서 돌아온 뒤 어떤 문장이 남아 있는가. 이 세 줄을 펼치면 “자기 자신을 호출한다”는 문장 뒤에 숨은 실행 순서가 보인다.