yeolyi.com성열의 컴퓨터공학

재귀

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

기둥에 쌓인 원반을 규칙에 맞게 다른 기둥으로 옮기는 하노이 탑 퍼즐이 있습니다. 원반이 3개면 손으로 풀지만, n개일 때 옮기는 순서를 출력하는 프로그램은 반복문으로 적기 막막합니다. 큰 문제를 같은 모양의 작은 문제로 줄여 푸는 방법을 쉬운 예부터 알아봅시다.

자기 자신을 부르는 함수

경우의 수 글에서 본 5!은 1부터 5까지 곱한 값입니다. 잘 보면 5!은 5 × 4!이고, 4!은 4 × 3!입니다. 그렇게 내려가다 1!에 닿으면 답은 1입니다. 이 관찰을 코드로 옮기면 다음과 같습니다.

1#include <stdio.h>
2
3int factorial(int n) {
4 if (n == 1) {
5 return 1;
6 }
7 return n * factorial(n - 1);
8}
9
10int main(void) {
11 printf("%d\n", factorial(4));
12 return 0;
13}

변수 없음
출력 없음

함수 안에서는 지금 호출의 n만 보입니다.

factorial 안에서 다시 factorial을 부릅니다. 이렇게 함수가 자기 자신을 부르는 것을 재귀(recursion)라 합니다. 재귀 함수는 두 부분으로 이루어집니다.

기저 사례가 없으면 호출이 끝없이 내려갑니다. 문제가 작아지다 반드시 기저 사례에 닿는지 확인해야 합니다.

쌓였다가 풀리는 호출

factorial(4)는 factorial(3)의 값을 받아야 4를 곱할 수 있습니다. factorial(3)도 factorial(2)를 기다립니다.

n
끝나지 않은 호출 (위가 가장 최근)
아직 없음

factorial(4)의 값을 구합니다.

끝나지 않은 호출이 위로 쌓였다가 factorial(1)부터 거꾸로 풀립니다. 가장 나중에 부른 호출이 가장 먼저 끝납니다. 스택 프레임 글에서 본 대로, 컴퓨터는 호출마다 스택 프레임을 쌓아 끝나지 않은 호출의 n을 따로 기억합니다.

하노이 탑

하노이 탑은 A 기둥에 큰 것부터 쌓인 원반을 모두 C 기둥으로 옮깁니다. 한 번에 맨 위 원반 하나만 옮길 수 있고, 작은 원반 위에 큰 원반을 올릴 수 없습니다.

A
B
C

옮길 원반이 있는 기둥을 누릅니다.0 / 최소 7

원반 3개를 C로 옮긴 뒤 4개로도 해 봅시다.

가장 큰 원반만 생각해 봅시다. 이 원반이 C의 바닥에 가려면 그 순간 나머지 n − 1개는 모두 B에 있어야 합니다. 그러니 순서가 정해집니다.

  1. 위의 n − 1개를 A에서 B로 옮깁니다.
  2. 가장 큰 원반을 A에서 C로 옮깁니다.
  3. B의 n − 1개를 C로 옮깁니다.

1과 3은 원반이 하나 적은 하노이 탑이고, 원반이 한 개면 그냥 옮기면 됩니다(기저 사례). 코드로 옮기면 다음과 같습니다.

// 원반 n개를 start에서 end로 옮긴다
void hanoi(int n, char start, char end,
           char via) {
    if (n == 1) {
        printf("%c → %c\n", start, end);
        return;
    }
    hanoi(n - 1, start, via, end);
    printf("%c → %c\n", start, end);
    hanoi(n - 1, via, end, start);
}

n − 1개를 어떻게 옮길지는 따지지 않고 같은 함수에 맡깁니다. n − 1개에서 맞으면 n개에서도 맞으니 수학적 귀납법의 귀납 단계와 같습니다.

A
B
C

"다음"을 눌러 재귀 풀이를 한 수씩 따라갑니다.0 / 최소 7

수마다 어느 호출 안에서 둔 수인지 보입니다.

n개를 옮기는 횟수는 n − 1개일 때의 두 배에 1을 더한 값이라 1, 3, 7, 15, …로 늘어 n개면 2ⁿ − 1번입니다. 시간 복잡도로는 O(2ⁿ)입니다.

도전 문제

원반 6개짜리 하노이 탑을 글의 방법대로 63번 만에 옮깁니다. 40번째 수에서 옮기는 원반은 작은 쪽에서 몇 번째 원반일까요? 가장 작은 원반이 1번째입니다. 숫자로 답하세요.