재귀 구조

본문

본문

기둥 세 개와 크기가 다른 원판들이 있다. 원판을 한 번에 하나씩 옮기되 큰 원판을 작은 원판 위에 올릴 수 없다는 규칙으로, 첫 기둥의 원판을 모두 셋째 기둥으로 옮겨야 한다. 전설에 따르면 어느 사원의 승려들이 원판 64개를 옮기고 있으며, 다 옮기는 날 세상이 끝난다고 한다. 원판 세 개는 몇 번 만에 옮길 수 있지만 64개는 왜 그렇게 오래 걸릴까? 이 문제를 프로그램으로 풀려면 어떻게 생각해야 할까?

원판의 수

그림 1. 원판 n개를 옮기는 최소 이동 횟수(로그 눈금). 원판이 하나 늘 때마다 이동 횟수가 두 배 남짓이 되어 직선으로 늘어난다.

먼저 알아야 할 것함수와 호출 스택(함수와 매개변수), 수열과 점화식(수학).

1.2.1더 작은 같은 문제로 넘기기

원판 n개를 첫 기둥에서 셋째 기둥으로 옮기려면 가장 큰 원판이 셋째 기둥 맨 아래로 가야 한다. 그러려면 그 위의 원판 n − 1개를 먼저 둘째 기둥으로 치워야 한다. 그다음 가장 큰 원판을 셋째 기둥으로 옮기고, 둘째 기둥의 n − 1개를 셋째 기둥 위로 옮긴다. 원판 n − 1개를 옮기는 일은 원판 n개를 옮기는 일과 같은 모양의 더 작은 문제이다. 이렇게 자기 자신을 더 작은 입력으로 부르는 함수를 재귀 함수라 한다. 원판이 하나뿐이면 그냥 옮기면 되므로, 그때 더 부르지 않고 멈춘다. 이 멈추는 경우를 기저 사례라 한다.

정리 1.2.1 하노이의 탑 이동 횟수

원판 \(n\)개를 옮기는 최소 횟수 \(T(n)\)은 \(T(1) = 1\), \(T(n) = 2T(n-1) + 1\)을 만족하며, 이 점화식을 풀면 \[T(n) = 2^n - 1\]이다. 재귀 함수는 기저 사례가 있어야 하고, 호출할 때마다 문제가 기저 사례 쪽으로 작아져야 끝난다.

그림 1에서 원판 수를 바꾸어 보자. 원판 3개는 7번, 10개는 1023번, 20개는 약 105만 번이다. 1초에 한 번 옮기면 원판 20개는 약 12일이 걸린다. 원판 64개는 \(2^{64} - 1 \approx 1.8 \times 10^{19}\)번으로, 1초에 한 번씩 옮기면 약 5850억 년이 걸린다. 우주의 나이 138억 년의 40배가 넘는다. 원판이 하나 늘 때마다 일이 두 배가 되기 때문이다.¹

1.2.2재귀로 생각하는 문제들

재귀는 문제의 구조가 자기 자신을 품고 있을 때 자연스럽다. 폴더 안에 폴더가 있는 파일 구조에서 모든 파일을 찾을 때, 수식 안에 괄호로 묶인 작은 수식이 있을 때, 리스트를 반으로 나누어 각각 정렬할 때가 그렇다. 재귀 함수를 짤 때는 세 가지를 확인한다. 기저 사례가 있는가, 재귀 호출마다 문제가 작아지는가, 작은 문제의 답으로 큰 문제의 답을 만들 수 있는가. 이 셋 가운데 하나라도 빠지면 함수가 끝나지 않거나 틀린 답을 낸다. 그리고 재귀 호출마다 스택 프레임이 쌓이므로, 너무 깊어지면 스택이 넘친다.

그림 2. 재귀 함수는 기저 사례, 작아지는 문제, 답의 조합 세 가지로 이루어진다.

1.2.3예제 풀이

예제 1.2.2

함수 하노이(n, 출발, 경유, 도착)를 재귀로 짰다. 하노이(3, "A", "B", "C")를 부르면 원판을 옮기는 출력이 몇 번 나오는가? 첫 세 번의 이동을 순서대로 쓰고, 이때 호출 스택이 가장 깊을 때 프레임은 몇 개인가?

\(T(3) = 2^3 - 1 = 7\)이므로 출력은 7번 나온다. 하노이(3)은 먼저 하노이(2, A, C, B)를, 그것은 하노이(1, A, B, C)를 부른다. 그래서 첫 이동은 A → C이다. 이어 원판 2를 A → B로 옮기고, 하노이(1, C, A, B)로 C → B를 옮긴다.

따라서 첫 세 번은 A → C, A → B, C → B로 작은 원판 둘이 B로 치워진다. 호출 스택은 하노이(3), 하노이(2), 하노이(1)이 쌓일 때 가장 깊어 3개이다. 원판이 n개이면 스택 깊이는 n이지만 이동 횟수는 \(2^n - 1\)이다. 즉 재귀 함수는 짧게 쓸 수 있어도, 그 일의 양은 호출이 만드는 나무의 크기만큼 늘어난다. 그래서 재귀 함수를 쓸 때는 호출이 몇 번 일어나는지 함께 따진다.

아래 탐구 카드에서 재귀 함수를 직접 짜 보고, 호출이 만드는 구조를 그려 보자.

하노이의 탑은 1883년 프랑스의 수학자 뤼카가 장난감으로 만들어 팔았고, 사원의 전설도 그때 함께 지어 붙인 이야기이다.

마무리

재귀 함수는 같은 모양의 더 작은 문제로 일을 넘기다가 기저 사례에서 멈추며, 작은 문제의 답으로 큰 문제의 답을 만든다. 하노이의 탑은 원판 n − 1개를 두 번 옮기고 가장 큰 원판을 한 번 옮기는 구조라 이동 횟수가 \(2^n - 1\)로 원판마다 두 배씩 늘어난다. 그래서 처음 질문의 원판 64개는 1초에 한 번 옮겨도 우주 나이의 40배가 넘게 걸려, 세상이 끝날 때까지 다 옮길 수 없다.

탐구 1

자기 자신을 부르는 함수는 왜 끝날 수 있을까?

재귀 함수 · 기저 조건 · 호출 스택 · 수학적 귀납법

n = 4

기저 조건(2–3번 줄) 지우기

지금 스택 깊이: 0
최대 깊이: 0
호출 횟수: 0

출력—

질문fact 함수는 몸체 안에서 다시 fact를 부른다. 부른 함수가 또 자기를 부르면 끝없이 이어질 것 같은데, 실제로는 24라는 답을 내고 끝난다. 언제, 어떻게 멈추는 것일까?
복원함수를 호출하면 새 프레임이 생기고, 함수가 끝나면 프레임이 사라지며 값이 호출한 곳으로 돌아간다. 수학에서 n! = n × (n − 1)!, 0! = 1이다.
설명자기 자신을 호출하는 함수를 재귀 함수라 한다. 재귀 함수에는 두 부분이 꼭 있어야 한다. 더 쪼개지 않고 바로 답을 내는 기저 조건과, 문제를 크기가 더 작은 같은 문제로 바꾸어 자기를 부르고 그 결과를 조합하는 재귀 단계이다. 호출이 이어질 때마다 프레임이 호출 스택에 쌓이고, 각 프레임은 자기만의 n을 가진다. 기저 조건에 닿으면 가장 나중에 쌓인 프레임부터 값을 돌려주며 차례로 빠진다.
연결재귀 함수는 수학적 귀납법과 같은 구조이다. 기저 조건은 귀납법의 첫 단계(n = 0일 때 성립)이고, 재귀 호출 fact(n - 1)은 귀납 가정(“n − 1에 대해서는 맞다”)에 해당한다. 그래서 재귀 함수를 설계할 때는 호출 과정을 끝까지 따라가지 않고, “더 작은 문제의 답은 재귀 호출이 이미 맞게 구해 준다”고 믿은 뒤 그 답으로 지금 문제를 어떻게 푸는지만 정하면 된다. 이 관계를 식으로 쓴 것이 재귀 관계 f(n) = n × f(n − 1)이다.
적용세 함수를 실행하며 오른쪽 식의 전개를 보자. 각 함수에서 재귀 관계는 무엇인가? 인자를 바꾸며 최대 스택 깊이를 기록해 보자. 팩토리얼과 리스트 합은 인자에 비례해 깊어지는데, 이진수 변환은 n을 64까지 키워도 왜 7을 넘지 않는가? ‘기저 조건 지우기’를 켜고 세 함수가 각각 어떻게 실패하는지 비교해 보자.
판단기저 조건이 있어도 인자가 그 조건에 다가가지 않으면 끝나지 않는다. fact(-1)은 n이 −2, −3, …으로 작아지기만 해서 n == 0에 닿지 못한다. 조건을 n <= 0으로 쓰거나 음수를 미리 걸러야 한다. 또 파이썬은 스택 깊이를 기본 1000 정도로 제한하므로, 깊이가 입력 크기에 비례하는 재귀는 큰 입력에서 RecursionError를 낼 수 있다.

확인조건이 달라지면

print가 재귀 호출 다음에 있다. count_down(3)은 무엇을 출력할까?

def count_down(n):
          if n == 0:
              return
          count_down(n - 1)
          print(n)

      count_down(3)

읽기 2

문제 속에서 재귀 관계를 어떻게 찾을까?

읽기 · 재귀 관계 · 귀납 가정 · 반복문을 재귀로 바꾸기

재귀 함수는 짧고 읽기 쉽지만, 처음 보는 문제에서 “자기 자신을 어떻게 부르지?”를 떠올리기는 어렵다. 재귀 관계를 찾는 데 쓸 수 있는 질문이 있을까?

1세 가지 질문

쪼개기

이 문제를 모양은 같고 크기만 더 작은 문제로 바꿀 수 있는가? (n → n − 1, 리스트 → 첫 원소를 뺀 리스트, n → n // 2)

조합하기

작은 문제의 답을 이미 안다고 가정하면, 그것으로 지금 문제의 답을 어떻게 만드는가?

멈추기

더 쪼갤 수 없는 가장 작은 문제는 무엇이고, 그 답은 바로 알 수 있는가?

두 번째 질문의 “이미 안다고 가정”이 수학적 귀납법의 귀납 가정이다. 귀납법에서 “n − 1일 때 성립한다고 가정하면 n일 때도 성립한다”를 보이듯, 재귀 함수에서는 “재귀 호출이 작은 문제를 맞게 풀어 준다고 믿으면 이 함수도 맞다”를 보이면 된다. 호출이 몇 단계로 이어지는지 머릿속으로 따라갈 필요가 없다.

문제	재귀 관계 (조합하기)	기저 조건 (멈추기)
거듭제곱 aⁿ	`power(a, n) = a * power(a, n - 1)`	n == 0 → 1
리스트 최댓값	`max(xs[0], biggest(xs[1:]))`	원소가 1개 → 그 원소
회문 판별	`s[0] == s[-1] and is_pal(s[1:-1])`	길이 0 또는 1 → True
최대공약수	`gcd(a, b) = gcd(b, a % b)` (유클리드 호제법)	b == 0 → a
하노이 탑 n개	위의 n − 1개를 보조 기둥으로 → 가장 큰 원판을 목표 기둥으로 → n − 1개를 목표 기둥으로. 이동 횟수 T(n) = 2T(n − 1) + 1	n == 0 → 옮길 것 없음 (T(0) = 0)

하노이 탑은 재귀 관계가 특히 잘 드러나는 예이다. 원판 n개를 옮기는 방법을 직접 떠올리기는 어렵지만, “n − 1개를 옮기는 방법은 이미 안다”고 가정하면 세 단계로 끝난다. 관계식을 풀면 T(n) = 2ⁿ − 1이므로, 원판 20개면 1,048,575번을 옮겨야 한다.

2회문 판별을 귀납 가정으로 읽기

def is_pal(s):
          if len(s) <= 1:                          # 기저 조건: 빈 문자열과 한 글자는 회문
              return True
          return s[0] == s[-1] and is_pal(s[1:-1])  # 양 끝이 같고, 가운데가 회문이면 회문

is_pal(s[1:-1])이 가운데 부분을 옳게 판정한다고 믿으면, 양 끝 글자가 같은지만 더 확인하면 된다. 인자의 길이가 매번 2씩 줄어 언젠가 1 이하가 되므로 반드시 기저 조건에 닿는다. 옳게 조합한다와 반드시 끝난다, 두 가지를 확인하면 재귀 함수가 옳다고 말할 수 있다.

3재귀 관계가 보이지 않을 때, 반복문을 재귀로 바꾸기

관계가 바로 보이지 않으면, 먼저 반복문으로 풀고 그것을 재귀로 옮겨 보는 것도 좋은 연습이다. 1부터 n까지의 합을 예로 들어 본다.

반복

def total_loop(n):
          s = 0
          for i in range(1, n + 1):
              s = s + i
          return s

재귀

def total_rec(n):
          if n == 0:
              return 0
          return n + total_rec(n - 1)

반복이 끝나는 조건(더 더할 수가 없음)이 기저 조건이 된다.
한 바퀴에 하는 일(i를 더함)이 조합이 되고, 남은 반복은 재귀 호출이 맡는다.
반복문에서 바뀌던 변수(i)는 재귀 함수의 매개변수가 된다.

누적 변수 s를 매개변수로 넘기는 방법도 있다. def total_acc(n, s=0):에서 n == 0이면 s를 돌려주고, 아니면 total_acc(n - 1, s + n)을 돌려준다. 반복문의 s를 그대로 옮긴 모양이라 변환하기 쉽다.

판단재귀 관계가 맞아도 효율은 따로 따져야 한다. xs[1:]와 s[1:-1] 같은 슬라이싱은 호출할 때마다 새 리스트·문자열을 복사하므로, 길이 n이면 복사에만 n²에 비례하는 시간이 든다. 시작 위치를 매개변수로 넘기면(biggest(xs, i)) 복사를 피할 수 있다. 같은 작은 문제를 여러 번 푸는 재귀는 더 큰 문제가 되는데, 이것은 다음 절에서 다룬다.

확인조건이 달라지면

자연수 n의 각 자리 숫자의 합(예: 472 → 13)을 구하는 재귀 함수 dsum(n)을 만들려고 한다. 기저 조건을 “n < 10이면 n을 돌려준다”로 둘 때, 재귀 단계로 옳은 것은?