[Recursion] 재귀 호출 기본 개념 및 예제

들어가며

완전 탐색을 할 때에 사용할 수 있는 방법 중 하나인 재귀 호출에 대해 공부해보고자 합니다. 이번 포스팅은 알고리즘 문제해결전략(구종만 저) 6장을 공부하며 정리한 내용입니다.

재귀 호출

재귀 함수(Recursive function)란, 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 의미합니다.

 

반복문을 재귀 함수로 바꿔 구현해보면, 재귀 호출의 기초적인 특징을 확인할 수 있습니다. 아래 예시에서는 기존 반복문 사용에 비해 재귀 호출의 이점이 별로 없지만, 기초적인 특징은 확인이 가능합니다.

 

1부터 n까지의 합을 구하는 반복문

int sum(int n) {
    int ret = 0;
    for(int i = 1; i <= n; i++)
        ret += i;
    return ret;
}

1부터 n까지의 합을 구하는 재귀 함수

int recursiveSum(int n) {
    if(n == 1) return 1;
    return n + recursiveSum(n-1);
}

• n개의 숫자의 합을 구하는 작업을 n개의 조각으로 쪼개, 더할 각 숫자가 하나의 조각이 되도록 합니다.
• n이 1이면 조각이 하나뿐이므로, 더 이상 작은 조각을 호출하면 안되므로, return 1을 할 수 있도록 조건문을 생성했습니다.
  • 모든 재귀 함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 합니다.
  • 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례(base case)라고 합니다.

위 기본 개념을 생각하며 아래 예제를 하나씩 풀어보겠습니다.

예제 | 중첩 반복문 대체하기

0번부터 차례대로 번호가 매겨진 n개의 원소 중 4개를 고르는 모든 경우의 수를 출력하는 코드를 작성합니다.
예를 들어, n=7이라면 (0,1,2,3), (0,1,2,4), (0,1,2,5),...,(3,4,5,6)의 경우의 수를 모두 출력해야 합니다.

n개의 원소 중 4개를 고르는 모든 조합을 찾는 반복문

for(int i = 0; i < n; i++)
    for(int j = i+1; j < n; j++)
        for(int k = j+1; k < n; k++)
            for(int l = k+1; l < n; l++)
                cout << i << " " << j << " " << k << " " << l << endl;

4개를 고르는 경우, for문을 4번 사용하면 구현은 가능합니다. 만약 5개를 고르는 경우라면, for문을 5번 사용하게 되는 등 중첩 for문 개수가 늘어나 코드가 길고 복잡해지게 됩니다.

 

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘

위 반복문에서 하는 작업은 네 개의 조각으로 나눌 수 있습니다. 각 조각에서는 하나의 원소를 고르면 됩니다.

이때 남은 원소를 고르는 작업은 아래와 같은 입력들의 집합으로 정의가 가능합니다.

• 원소들의 총 개수(int n)
• 더 골라야 하는 원소 개수(int noPickCnt)
• 지금까지 고른 원소 번호 집합(vector<int>& picked)

void pick(int n, int noPickCnt, vector<int>& picked) {
    // 원소를 다 골랐다면, 골라진 원소들을 출력하기 위해 printPicked 메소드 호출
    if(noPickCnt == 0) {
        printPicked(picked);
        return;
    }
    
    // 현재까지 고른 원소들의 제일 큰 값 + 1을 현재 뽑을 수 있는 시작 원소로 지정
    int startPickNum = 0;
    if(!picked.empty())
        startPickNum = picked.back() + 1;
        
    // 위에서 지정한 시작 원소부터 하나씩 현재까지 고른 원소들 백터에 넣음
    // 이번 조각에서 특정 원소를 넣고 다음 단계로 넘어갈 재귀를 호출한 뒤, 이번 조각을 비워 다른 원소를 넣는 식으로 진행
    for(int next = startPickNum; next < n; next++) {
        picked.push_back(next);
        pick(n, noPickCnt - 1, picked);
        picked.pop_back();
    }
}

• 위 알고리즘의 경우, 기존 중첩 반복문과 달리 몇 개의 원소를 고르냐에 따라 코드가 변하지 않고 메소드에 들어갈 입력값만 변경하면 됩니다.

예제 | 보글 게임(문제 ID: BOGGLE, 난이도: 하)

보글은 아래 그림과 같이 5X5 크기의 알파벳 격자를 가지고 하는 게임입니다. 이 게임의 목적은 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것입니다. 예를 들어 아래와 같이 알파벳이 들어있다면 PRETTY, GIRL, REPEAT 등의 단어를 찾을 수 있습니다. 각 글자들은 대각선으로도 이어질 수 있으며, 한 글자가 두 번 이상 사용될 수 있습니다.

단어가 주어졌을 때, 해당 단어를 5X5 알파벳 격자에서 찾을 수 있는지 여부를 출력해야 합니다.
hasWord(y, x, word) 메소드는 보글 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부를 반환합니다.

알파벳 격자 예시

찾아낼 수 있는 단어 예시

hasWord()가 하는 일을 가장 쉽게 조각내는 방법은, 단어 내 각 글자를 하나의 조각으로 보는 것입니다.

(처음 이 문제를 보았을 때에는, word가 주어지지 않은 채로 찾는 것인 줄 알고 헤매었는데 단어가 주어지는 상황이면 쉽게 풀이가 가능해보입니다)

• 각 조각에서는 현재 가진 word의 첫 자리와 현 위치의 글자가 동일한 지 판단하면 됩니다.
  • 해당 조각이 동일하면 거기서 다시 한 번 자기 자신을 호출하면 되고, 동일하지 않다면 거기서 false로 return하면 됩니다.

기저 사례의 선택

더 이상 탐색 없이 답을 낼 수 있는 아래 경우들을 기저 사례로 선택합니다.

1. 위치 (y, x)가 보글 게임판을 벗어난 경우 실패
2. 위치 (y, x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
3. (2번 경우에 해당하지 않은 경우) 원하는 단어가 한 글자인 경우 항상 성공

보글 게임판에서 단어를 찾는 재귀 호출 알고리즘

// 보글 게임판에서 인접한 8칸 검사를 하기 위해 사용하는 배열
const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1};

bool hasWord(int y, int x, const string& word) {
    // (y, x)가 보글 게임판을 벗어난 위치면 false (기저 사례 1)
    if(!inRange(y, x)) return false;
    // 첫 글자가 일치하지 않으면 false (기저 사례 2)
    if(board[y][x] != word[0]) return false;
    // 단어 길이가 1이면 true (기저 사례 3) > 첫 글자가 일치하면서 단어 길이가 1이라면 초기에 주어진 word가 있는 것
    if(word.size() == 1) return true;
    // (y, x) 인접한 8칸 검사
    for(int i = 0; i < 8; i++) {
        int nextY = y + dy[i];
        int nextX = x + dx[i];
        // 이번 위치의 글자는 주어진 word와 동일하므로, word 내 다음 글자부터 보기 위해 word는 substr(1) 메소드를 통해 쪼갠 후 넘김
        if(hasWord(nextY, nextX, word.substr(1))) return true;
    }
    return false;
}

• 위에서 미리 선택한 기저 사례 선택을 이용해 코드를 작성한 것입니다. hasWord()의 경우 (y, x) 위치의 글자를 현재 확인해야 하는 word내 글자와 비교하여 원하는 단어가 보글 게임판 내에 있는지 확인합니다.

완전 탐색 레시피

어떤 문제를 완전 탐색으로 해결하기 위해 필요한 과정은 아래와 같습니다. 해당 과정이 모든 문제에 항상 적용되는 것은 아니지만, 어떤 식으로 문제에 접근해야 할지에 대한 대략적인 지침이 될 수 있습니다.

1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 비례합니다. 따라서, 최대 크기 입력을 가정했을 때의 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있는지 가늠해야 합니다.
   • 만약 시간 안에 계산할 수 없다면 다른 방식을 이용해야 합니다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눕니다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 됩니다.
3. 그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성합니다.
4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리합니다.