[DS] 7. 순환(재귀)

순환(재귀; recursion)?

int factorial(int n)
{ 
  if (n <= 1)
    return 1;
  
  return n * factorial(n - 1);
}

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법.

순환(재귀)은 큰 문제를, 동일한 형태의 작은 문제로 나누어 해결하는 방법이다. 팩토리얼 / 피보나치 수열 / 하노이의 탑 등이 대표적인 예시.

순환 함수는 일반적으로 다음 두 부분으로 구성된다.

구성	설명
기본 조건(Base Case)	더 이상 순환 호출하지 않고 결과를 반환하는 조건.
순환 조건(Recursive Case)	문제의 크기를 줄여 자기 자신을 다시 호출하는 부분.

기본 조건이 없거나 도달할 수 없는 조건이라면 함수의 호출이 계속되며, 이 경우 시스템의 스택¹ 공간이 부족해 스택 오버플로우(Stack Overflow)가 발생할 수 있다.

---

순환과 시스템 스택

함수가 호출되면 매개변수, 지역 변수, 복귀 주소 등의 관련 정보가, 시스템 스택의 스택 프레임(Stack Frame)에 저장된다.

순환(재귀) 함수는 호출 깊이에 따라 새로운 스택 프레임을 계속 쌓는다. 팩토리얼을 예시로 든다면 아래와 같다.

factorial(3)

factorial(3)에서 시작해, 그 내부에서 factorial(2), factorial(1) 꼴로 단계 호출되어 마지막에서 결과를 반환하면, 가장 나중에 호출된 함수부터 다음과 같이 차례로 종료된다.

factorial(1) → 1
factorial(2) → 2 × 1
factorial(3) → 3 x 2 → 6 

이처럼 순환 호출은 시스템 스택을 이용하여 후입선출(LIFO) 방식으로 처리된다.

---

반복문과의 비교

대부분의 순환(재귀) 함수는 반복문을 사용하는 구조로 바꿀 수 있다.

int factorial(int n)
{
  int result = 1;
  
  for (int i = 2; i <= n; ++i)
    result *= i;
  
  return result;
}

일반적으로 순환으로 구현한 함수는 반복문으로 변환하면 가독성이 떨어지는 경우가 많다. 때문에 용도에 따라서는, 직관성을 위해서 의도적으로 순환 형태로 두는 편이다.

반복문은 순환처럼 자체적으로 호출 단계가 깊어지지는 않기에, 스택 프레임을 추가로 만들지 않는다. 이로 인해 오버헤드가 덜한 경우가 많다.

다만 현대에서는 최적화를 위해 굳이 반복문으로 수동 변환할 필요성이 낮다. 최적화를 위해 컴파일러가 알아서 반복문으로 변환하기도 하기 때문.

---

사례

거듭제곱

가장 단순한 거듭제곱 계산은 밑 x를 n번 곱하는 방법이다.

int power(int x, int n)
{
  int result = 1;

  for (int i = 0; i < n; ++i)
    result *= x;

  return result;
}

이 방법은 n번의 곱셈이 필요하므로 시간 복잡도는 $O(n)$이다.

지수의 성질을 이용하면 문제의 크기를 절반씩 줄일 수 있다.

\[x^n = \begin{cases} 1 & n = 0 \\ (x^{n/2})^2 & n\text{이 짝수} \\ x \times (x^{n/2})^2 & n\text{이 홀수} \end{cases}\]

int power(int x, unsigned int n)
{
  if (n == 0)
    return 1;

  int half = power(x, n / 2);

  if (n % 2 == 0)
    return half * half;

  return x * half * half;
}

호출마다 지수 n이 절반으로 줄어들기 때문에 시간 복잡도는 $O(\log n)$이다. 문제를 절반으로 나누는 분할 정복(Divide and Conquer) 알고리즘을 사용했기 때문.

같은 알고리즘을 반복 구조로 구현하는 것도 가능하다.

---

피보나치 수열

피보나치 수열은 앞의 두 항을 더해 다음 항을 만드는 수열이다.

\[F_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F_{n-1} + F_{n-2} & n \ge 2 \end{cases}\]

int fibonacci(int n)
{
  if (n <= 1)
    return n;

  return fibonacci(n - 1) + fibonacci(n - 2);
}

코드는 간단하지만 같은 값을 여러 번 계산한다는 문제가 있다.

예시로 fibonacci(5)를 계산할 때 fibonacci(4)와 fibonacci(3)을 호출하며, 두 호출 내부에서 fibonacci(2), fibonacci(1)와 같은 계산이 반복된다.

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  └─ fib(2)
└─ fib(3)
   ├─ fib(2)
   └─ fib(1)

따라서 단순 순환 구현의 시간 복잡도는 지수적으로 증가한다. 즉 $O(2^n)$꼴이다. 이는 인자가 조금만 커져도 연산이 불가능에 가까워질 정도로 부하가 심각해지는 원인이 된다.

반복 구조를 이용하면 이미 계산한 두 항만 저장하면서 중복 계산을 제거할 수 있다.

int fibonacci(int n)
{
  if (n <= 1) return n;

  int previous = 0; // 이전 값 저장
  int current = 1;  // 현재 값 저장

  for (int i = 2; i <= n; ++i)
  {
    int next = previous + current; // 이전/현재 값으로 현재 값 갱신
    previous = current;
    current = next;
  }

  return current;
}

이 구현의 시간 복잡도는 $O(n)$이고, 추가 공간 복잡도는 $O(1)$이다.

이와 같이, 이미 계산한 값을 저장하는 방식(메모이제이션)으로 순환 구조를 유지하면서 중복 계산을 제거할 수도 있다.

---

하노이의 탑

하노이의 탑은 다음 규칙에 따라 한 막대에 쌓인 원판들을 다른 막대로 옮기는 문제이다.

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 가장 위에 있는 원판만 옮길 수 있다.
3. 큰 원판을 작은 원판 위에 놓을 수 없다.

n개의 원판을 from 막대에서 to 막대로 옮기고, temp 막대를 보조로 사용한다고 가정한다. 이를 코드적인 관점에서 과정을 생각하면 다음과 같다.

1. 맨 아래 원판을 제외한 n - 1개의 원판을 from에서 temp로 옮긴다.
2. 맨 아래 원판을 from에서 to로 옮긴다.
3. temp에 있는 n - 1개의 원판을 to로 옮긴다.

void hanoi(int n, char from, char temp, char to)
{
  if (n == 1)
  {
    std::cout << from << " -> " << to << std::endl;
    return;
  }

  hanoi(n - 1, from, to, temp);
  std::cout << from << " -> " << to << std::endl;
  hanoi(n - 1, temp, from, to);
}

하노이의 탑은 하나의 문제에서, 크기가 작은 문제를 두 번 호출하므로 이진 순환에 해당한다.

n개의 원판을 옮기는 데 필요한 최소 이동 횟수는 $2^n - 1$이다. 즉 시간복잡도는 $O(2^n)$이다.

---

다중 순환

순환 함수는 호출 시 마다 몇 개의 순환 호출이 이루어지는지에 따라 아래와 같이 구분 가능하다.

종류	설명	예시
선형 순환	한 번의 실행에서 하나의 순환 호출을 수행	팩토리얼, 거듭제곱
이진 순환	한 번의 실행에서 두 개의 순환 호출을 수행	피보나치 수열, 하노이의 탑
다중 순환	한 번의 실행에서 여러 개의 순환 호출을 수행	영역 채색, 미로 탐색

영역 채색 문제

영역 채색(blob coloring)은 이진(흑과 백만 갖는) 영상이나 격자에서 서로 연결된 영역을 찾는 방법이다.

영상을 순회하다 흰색 화소를 발견하면 해당 화소를 특정 색으로 칠하고, 상하좌우에 위치한 이웃 화소를 순환적으로 검사한다.

constexpr int WIDTH = 20;
constexpr int HEIGHT = 9;
constexpr int BACKGROUND = 0;
constexpr int UNVISITED = -1;

void labelComponent(int image[HEIGHT][WIDTH], int x, int y, int label)
{ // 범위 내가 아니라면 return
  if (x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT)
    return;

  // 처리된 화소라면 return
  if (image[y][x] != UNVISITED)
    return;

  // 현재 화소에 영역 번호 부여
  image[y][x] = label;

  // 좌우상하의 이웃 화소를 순환적으로 검사 (다중순환)
  labelComponent(image, x - 1, y, label);
  labelComponent(image, x + 1, y, label);
  labelComponent(image, x, y - 1, label);
  labelComponent(image, x, y + 1, label);
}

void labelAllComponents(int image[HEIGHT][WIDTH])
{
  int label = 1;

  // 순회
  for (int y = 0; y < HEIGHT; ++y)
    for (int x = 0; x < WIDTH; ++x)
      if (image[y][x] == UNVISITED)
        labelComponent(image, x, y, label++);
}

void printImage(const int image[HEIGHT][WIDTH])
{ // 배경은 '.', 미처리 화소는 '#', 처리된 영역은 번호로
  for (int y = 0; y < HEIGHT; ++y)
  {
    for (int x = 0; x < WIDTH; ++x)
      if      (image[y][x] == BACKGROUND)  std::cout << " .";
      else if (image[y][x] == UNVISITED)   std::cout << " #";
      else                                 std::cout << ' ' << image[y][x];
    std::cout << std::endl;
  }
}

예제 main 코드

int main()
{
  constexpr const char* SOURCE[HEIGHT] = {
    "..##....###.",
    "..##....#...",
    "......###...",
    ".###........",
    ".#.#...##...",
    ".###...##...",
    "............"
  };

  int image[HEIGHT][WIDTH] = {};

  // # -> UNVISITED 변환
  for (int y = 0; y < HEIGHT; ++y)
    for (int x = 0; x < WIDTH; ++x)
      image[y][x] = (SOURCE[y][x] == '#' ? UNVISITED : BACKGROUND);

  // Origin 출력 - 변환 - Labelled 출력
  std::cout << "<Original image>\n";
  printImage(image);

  labelAllComponents(image);

  std::cout << "\n<Labelled image>\n";
  printImage(image);
}

<Original image>
 . . # # . . . . # # # .
 . . # # . . . . # . . .
 . . . . . . # # # . . .
 . # # # . . . . . . . .
 . # . # . . . # # . . .
 . # # # . . . # # . . .
 . . . . . . . . . . . .

<Labelled image>
 . . 1 1 . . . . 2 2 2 .
 . . 1 1 . . . . 2 . . .
 . . . . . . 2 2 2 . . .
 . 3 3 3 . . . . . . . .
 . 3 . 3 . . . 4 4 . . .
 . 3 3 3 . . . 4 4 . . .
 . . . . . . . . . . . .

미로 탐색 문제

미로 탐색 또한 std::stack 기반의 깊이 우선 탐색(DFS) 대신 순환으로 구현할 수 있다.

현재 위치를 방문 처리한 뒤 상하좌우의 다음 위치에 대해 탐색 함수를 호출하는 방식.

constexpr int MAZE_SIZE = 6;
constexpr char PATH = '0';
constexpr char EXIT = 'x';
constexpr char VISITED = '5';

bool isValidLocation(
  const char maze[MAZE_SIZE][MAZE_SIZE],
  int row, int column)
{ // 범위가 유효한지 검사. 사이즈 내인가.
  if (row < 0 || row >= MAZE_SIZE || column < 0 || column >= MAZE_SIZE)
    return false;
  return maze[row][column] == PATH || maze[row][column] == EXIT;
}

bool searchMaze(
  char maze[MAZE_SIZE][MAZE_SIZE],
  int row, int column)
{
  std::cout << '(' << row << ", " << column << ") ";

  // 현재 위치가 출구라면 탐색 성공
  if (maze[row][column] == EXIT)
    return true;

  // 현재 위치를 방문 처리
  maze[row][column] = VISITED;

  // 상하좌우의 이웃 위치를 순환적으로 탐색
  if (isValidLocation(maze, row - 1, column) &&
      searchMaze(maze, row - 1, column))
    return true;
  if (isValidLocation(maze, row + 1, column) &&
      searchMaze(maze, row + 1, column))
    return true;
  if (isValidLocation(maze, row, column - 1) &&
      searchMaze(maze, row, column - 1))
    return true;
  if (isValidLocation(maze, row, column + 1) &&
      searchMaze(maze, row, column + 1))
    return true;

  // 모든 방향에서 출구를 찾지 못함
  return false;
}

예제 main 코드

int main()
{
  constexpr int ENTRY_ROW = 1;
  constexpr int ENTRY_COLUMN = 0;

  char maze[MAZE_SIZE][MAZE_SIZE] = {
    {'1', '1', '1', '1', '1', '1'},
    {'e', '0', '1', '0', '0', '1'},
    {'1', '0', '0', '0', '1', '1'},
    {'1', '0', '1', '0', '1', '1'},
    {'1', '0', '1', '0', '0', 'x'},
    {'1', '1', '1', '1', '1', '1'}
  };

  const bool isFound = searchMaze(maze, ENTRY_ROW, ENTRY_COLUMN);

  std::cout << "\n"
            << (isFound ? "출구 찾음" : "출구 못찾음") << std::endl;
}

(1, 0) (1, 1) (2, 1) (3, 1) (4, 1) (2, 2)
(2, 3) (1, 3) (1, 4) (3, 3) (4, 3) (4, 4) (4, 5)
출구 찾음.

막다른 길에 다다를 시, 이전 호출로 되돌아가 다른 방향을 탐색한다. 이는 깊이 우선 탐색과 본질적으로 같다.

---

1. 여기서 말하는 스택은 자료구조의 Stack이 아닌, 시스템 내부 저장공간(코드/데이터/힙/스택) 중 하나인 스택을 뜻한다. 스택에는 함수 호출 정보들과 그 안의 임시 변수들(지역/매개변수 등)이 담기게 된다. ↩︎