[C++ 코딩테스트 연습] 3. 재귀함수

---

1. 재귀의 정의

재귀란 자기 자신을 정의하거나 호출하는 것을 말한다. 프로그래밍에서는 함수가 실행 중에 자기 자신을 다시 호출하는 방식의 함수를 말한다. 재귀함수는 호출되고 나서 언젠가 반드시 종료되어야 한다.

그럼 왜 재귀함수를 사용해야 하는 걸까?

문제를 더 작은 크기의 문제의 해를 이용해 해결하고, 그렇게 하다가 더 이상 줄일 수 없을 정도로 작아진 문제의 해를 직접 구하기 위해서이다.

 

---

1) 재귀 함수 설계

(1) 팩토리얼의 사례

N! 을 Fact(N)으로 표현한다면,

Fact(N) = N * Fact(N-1) 로 표현할 수 있다.

Fact(N-1) = N-1 * Fact(N-2) 로 표현할 수 있으니까, 둘을 합치면, Fact(N) = N * (N-1) * Fact (N-2) 가 되는 것이다.

이걸 계속 반복하다보면 결국 1! 이 나오게 되고, 더이상 작게 할 수 없으므로 1을 반환하게 만들면 된다.

#include <iostream>
using namespace std;
// 팩토리얼을 구하는 재귀 함수
int Fact(int N) {
 if (N == 0 || N == 1) return 1; // 종료 조건 (0! = 1)
 return N * Fact(N - 1); // 재귀 호출
}
int main() {
 int num = 5;
 cout << num << "! = " << Fact(num) << endl;
 return 0;
}
/*
출력 결과:
5! = 120
*/

 

이처럼 재귀함수는 첫 번째 기저 조건을 충족(즉, 가장 작아진 문제의 해를 직접 구할 수 있으면)하면, k번째 함수가 실행되었을 때 k+1 번째 함수가 반드시 실행된다는 특징을 이용할 수 있다.

 

(2) 메모리

다만 성능 및 메모리를 고려해야 한다. 재귀 함수가 반복적으로 호출되면 각각의 호출마다 새로운 스택 프레임이 생성되어 스택 메모리에 쌓인다. 그리고 최종적으로 마지막 함수(가장 작아진 문제의 해, 첫 번째 기저 조건)까지 호출이 완료되면 각 함수는 자신을 호출했던 위치로 되돌아가면서 종료된다.

이 과정에서 재귀 함수가 호출될 때마다 스택 메모리에 함수의 실행 정보가 저장되는데, 과도하게 누적되다보면 스택 오버플로우가 발생할 수 있다. 

성능 및 메모리를 위해서라면 종료 조건을 명확히 정의하고 호출 깊이를 적절히 제한해서 메모리 사용을 관리해야 한다.

 

-> 종료 조건 명확히 정의하기 : 기저 조건 설정하기

-> 호출 깊이 제한하기 : 메모이제이션 사용하기

 

2) 재귀 함수 사용

일반적으로 대부분의 반복 작업은 반복문으로 구현한다. 그럼에도 재귀를 사용하는 것이 더 효율적인 경우는 뭘까.

 

(1) 깊이 우선 탐색 알고리즘(DFS)

함수의 호출 과정은 스택 구조를 따르고, 가장 최근에 호출된 함수부터 가장 먼저 종료된다. 이를 이용해서 스택 기반 알고리즘의 대표적인 사례인 깊이 우선 탐색 알고리즘(Deep-First Search)을 구현할 수 있다.

DFS는 현재 노드를 방문 처리하고, 인접한 노드 중 방문하지 않은 노드를 재귀적으로 방문한다. 이후 더 이상 방문할 노드가 없으면 이전 노드로 되돌아간다. 즉, 각 함수는 자신과 인접한 노드의 관리만 하면 되므로 코드의 가독성과 유지보수성이 향상된다. 

#include <iostream>
#include <vector>
using namespace std;
// 그래프를 인접 리스트로 표현
vector<int> graph[9];
bool visited[9];

// DFS 함수 정의
void DFS(int node) {
 visited[node] = true;
 cout << node << ' ';
 for (int i = 0; i < graph[node].size(); i++) {
 int next = graph[node][i];
 if (!visited[next]) {
 DFS(next);
 }
 }
}
int main() {
 // 그래프 초기화
 graph[1] = {2, 3, 8};
 graph[2] = {1, 7};
 graph[3] = {1, 4, 5};
 graph[4] = {3, 5};
 graph[5] = {3, 4};
 graph[6] = {7};
 graph[7] = {2, 6, 8};
 graph[8] = {1, 7};
 // DFS 실행
 DFS(1);
 return 0;
}
/*
출력 결과:
1 2 7 6 8 3 4 5
*/

 

게임 개발에 사용되는 사례를 살펴본다면,

 

미로 생성 알고리즘 :

미로의 출구를 기저 조건이라고 생각해보면, 무작위 방향으로 이동하며 벽을 뚫고 막다른 길에 도달하면 다시 이전 갈림길로 돌아와 다른 방향(방문하지 않은 노드의 방향)으로 뚫게 만든다. 최종적으로는 미로의 출구에 도달하게 된다면 반드시 하나의 경로만 존재하는 미로를 만들 수가 있다.

 

대화 시스템 및 퀘스트:

보통 RPG 게임에서 선택지 시스템을 구현할 때 DFS 구조를 사용할 수 있다. 대화의 흐름을 트리 구조로 관리하기 때문에, 선택지에 따른 결말을 관리하거나, 특정 대화가 끝난 뒤 다시 이전 갈림길(상위 선택지)로 돌아와야 할 때 노드를 탐색하며 대화 내용을 불러오게 할 수 있다.

 

퍼즐 게임 :

AI가 퍼즐을 풀어나가는, 혹은 플레이어에게 힌트를 주고 싶을 때 사용할 수 있다. 현재 상태에서 가능한 수를 두고 그 다음 가능한 수를 계속 파고드는 형식이다. 정답(승리)을 기저 조건으로 두고 계속 해답을 찾아나가는 방식이다.

 

RTS 게임 : 

플레이어가 유닛을 이동시킬 때의 길찾기 시스템에 활용될 수 있다. 가장 빠른 이동 경로를 찾거나 막힌 길을 판단할 때 사용할 수 있다.

 

(2) 분할 정복 알고리즘(Divide and Conquer)

분할 정복 알고리즘은 문제를 작게 나누고 동일한 방법으로 해결한 뒤에 결과를 결합해서 전체 문제를 푸는 방식이다. 사람이 머리를 회전시킬 때를 생각해서 대입해보면, 복잡하고 거대한 문제를 마주했을 때 감당 가능한 수준으로 쪼갠다음에 푸는 것이라고 봄면 될 것 같다. 대표적인 사례로 병합 정렬이 있다. 계속 절반으로 쪼개나가면서, 각 부분 배열을 재귀적으로 병합 정렬하고 최종적으로는 정렬된 부분 배열을 병합하여 하나의 정렬된 배열로 만드는 것이다.

 

게임 개발에 사용되는 사례를 살펴본다면, 주로 성능 최적화와 무한한 배경 생성 분야에 사용된다.

 

1. 광범위한 충돌 감지

대규모의 유닛이 서로 부딪히는지 확인하는 경우에, 연산량이 기하급수적으로 늘어나지 않게 하도록 분할 정복을 활용한 쿼드트리(Quadtree)를 활용한다. 전체 맵을 4개의 구역으로 나누고 각 구역에 유닛이 너무 많으면 다시 4개로 쪼개고, 재귀적으로 반복하여 유닛이 적당히 적은 상태가 되면 같은 구역에 있는 유닛끼리만 충돌 계산을 하게 만드는 식이다. 충돌 걱정이 없는 구역에 있는 유닛 까지 충돌 계산을 할 필요는 없다. 불필요한 계산을 줄여 프레임을 방어하는데 사용한다.

 

2. 대규모 유닛의 경로 탐색

비슷한 논리로 대규모 유닛의 경로 탐색도 가능하다. 수백 명의 병사를 이동시킬 때 모든 타일을 전부 계산하면 연산량이 너무나 커지게되므로, 맵을 여러 개의 구역(Chunk)으로 나누어 계산하는 것이다. 구역과 구역 사이의 큰 길부터 찾고, 그 안에서 세부적인 경로를 찾아 최종적으로 경로들을 취합한다.

 

3. 절차적 지형 생성

마인크래프트처럼 무작위 지형을 만들 때 다이아몬드-스퀘어 알고리즘을 사용한다. 큰 지형에서 시작해서 세부적인 굴곡으로 파고드는 전형적인 분할 정복 방식이다. 큰 사각형의 네 꼭짓점 높이를 정하고, 중심점의 높이를 네 점의 평균값에 무작위 변수를 더해 결정한다. 계속 재귀적으로 반복해서 큰 돌덩어리를 자연스러운 굴곡을 가진 산과 계곡으로 변하게 한다고 보면 된다.

 

3) 재귀 함수 사용시 주의점

(1) 중복되는 함수 호출

함수가 중복되어 호출되다보니 호출되는 함수의 수가 급격히 증가하면서 금방 메모리를 고갈시킬 수 있다.

그래서, 이미 계산한 함수의 결과를 저장해두고, 그 다음에는 다시 계산하지 않고 결과값만 불러오는 메모이제이션을 사용한다.

#include <iostream>
#include <vector>
using namespace std;
// 메모이제이션을 위한 배열 초기화
vector<int> memo(1000, -1);
// 피보나치 수열을 메모이제이션을 활용하여 재귀적으로 계산하는 함수
int fibo(int n) {
 if (n == 1 || n == 2) return 1;
 if (memo[n] != -1) return memo[n];
 memo[n] = fibo(n - 1) + fibo(n - 2);
 return memo[n];
}
int main() {
 int n = 10;
 cout << "fibo(" << n << ") = " << fibo(n) << endl;
 return 0;
}
/*
출력 결과:
fibo(10) = 55
*/

메모이제이션을 위해서 vector<int> memo(1000, -1); 처럼 컨테이너를 만들어 초기화를 시켰고, 재귀 함수의 결과값이 나올때마다 벡터 컨테이너에 저장해두게 한다.

만약 함수의 결과값이 memo에 이미 있다면, 그냥 memo[n] 을 불러온다. -> if (memo[n] != -1)

 

(2) 성능 개선하기

X의 N승을 반환하는 함수를 재귀로 구현해본다고 하자.(N은 음이 아닌 정수)

X의 0승은 1이므로 1은 기저 조건이 된다. 따라서 X의 0승은 직접 반환한다.

이때 X의 N승을 계산하는 함수 pow(X,N)이 있다고 가정하면, pow(X,N) = pow(X, N-1) * X 이다.

 

이때 N이 짝수일 경우, pow(X,N) = pow(X, N/2)^2 형식으로도 나타낼 수 있다. 즉, 문제의 크기를 절반으로 바로 줄여버려서 재귀 호출 횟수와 연산 횟수를 대폭 감소시키는 것이다. 이런 논리는 꽤 많이 사용하므로 잘 숙지해두면 좋을 것 같다.

#include <iostream>
using namespace std;
// X의 N승을 계산하는 분할 정복 재귀 함수
double pow(double X, int N) {
 if (N == 0) return 1; // 기저 조건: X^0 = 1
 double half = pow(X, N / 2); // X^(N/2) 계산
 if (N % 2 == 0) {
 return half * half; // N이 짝수인 경우: X^N = (X^(N/2))^2
 } else {
 return half * half * X; // N이 홀수인 경우: X^N = (X^(N/2))^2 * X
 }
}
int main() {
 double X = 2.0;
 int N = 10;
 cout << "pow(" << X << ", " << N << ") = " << pow(X, N) << endl;
 return 0;
}
/*
출력 결과:
pow(2, 10) = 1024
*/

이처럼 조건문을 달아서, N이 짝수이면 N을 2로 나눈 값을 사용해서 연산을 대폭 줄이고, N이 홀수이면 N이 짝수인 경우처럼 절반을 줄여서 계산하고 X를 한번 더 곱해주면 된다. 

 

---

 

*오늘의 코드카타*

--

함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해양 합니다. 조건을 만족하는 함수 solution을 완성해주세요.

 

x는 -10000000 이상, 10000000이하의 정수입니다. 

n은 1000 이하인 자연수입니다.

 

==

C언어에서는 지난번에 배웠던 것처럼 malloc을 이용해서 공간을 확보한 뒤 값을 도출해내야 한다.

그러나 이번 문제에서는 기본적으로 vector가 포함되어있다. 즉, C++ 라이브러리 기능을 활용해서 작성하는 것을 권장한다는 뜻이다.

 

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(int x, int n) {
    vector<long long> answer;
    
    answer.reserve(n);
    
    for (int i = 1; i <= n; i++) {
        answer.push_back((long long)x * i);
    }
    
    return answer;
}

vector 컨테이너를 선언한다. 이때 x 값이 계산 도중 커질 수 있으므로 64비트 정수형인 long long을 사용한다.

계산된 값을 push_back을 이용해서 컨테이너의 맨 끝에 계속 밀어넣을 것이다.

문제에서 제시한 조건을 x*1, x*2, x*3, .... x*(n-1), x*n 식으로도 표현할 수 있으므로, x * i 를 i = 1~n 으로 반복한 후에 그 값을 밀어넣는 것과 같다.