[알고리즘] 재귀 호출, 재귀 함수란?

컴퓨터가 수행하는 많은 작업들은 대개 작은 조각들로 나누어 볼 수 있다.

예를 들어, 문자열의 길이를 세는 작업은 첫 한 글자를 세기, 다음 한 글자 세기, 다음 한글자를 세기 ... 라는 조각들로 나눌 수 있을 것이다.

이런 작업을 구현할 때 유용하게 사용되는 개념이다.

 

재귀 함수 (recursive function) or 재귀 호출 (recursion)

자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

 

코드

1부터 n까지의 합을 계산하는 반복 함수(sum)과 재귀 함수(recursiveSum)

 

// 필수 조건 : n >= 1
// 결과 : 1부터 n까지의 합을 반환한다.
int sum(int n) {
	int ret = 0;
	for (int i = 1; i <= n; ++i)
		ret += i;
	return ret;
}

// 필수 조건 : n >= 1
// 결과 : 1부터 n까지의 합을 반환한다.
int recursiveSum(int n) {
	if (n == 1) return 1; // 더이상 쪼개지지 않을 때
	return n + recursiveSum(n - 1);
}

 

재귀 호출을 이용하기 위해서,

n개의 숫자의 합을 구하는 작업을 n개의 조각으로 쪼개, 더할 각 숫자가 하나의 조각이 되도록 하자.

 

이 조각 중에 n만 따로 빼서 본다면, 나머지는 1부터 n-1까지의 조각들이 남는다.

 

나머지는 결국 1부터 n-1까지의 합이다. 따라서 자기 자신을 호출하여 n-1까지의 합을 구하고, 여기에 n을 더하면 우리는 원하는 답을 얻을 수 있다.

 

n이 1인 경우 조각이 하나 뿐이기 때문에, 곧바로 1을 반환하는 조건문을 추가한다.

 

기저 사례 (base case)

재귀 함수는 더이상 쪼개지지 않는 최소한의 작업에 도달했을 때 답을 곧바로 반환하는 조건문을 포함해야 한다. 이때 쪼개지지 않는 가장 작은 작업들을 뜻한다.

 

기저 사례를 선택할 때는, 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 해야 한다.

 

ex) recursiveSum()에서 n이 2인지 확인하여 3을 반환하는 경우, 입력이 1이 들어오면 문제가 생기게 된다.

따라서 기저 사례는 n==1인 경우에 1을 반환하는 것이 옳다.

 

 

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

보글(Boggle)은 그림과 같은 5*5 크기의 알파벳 격자를 가지고 하는 게임이다. 이때 게임의 목적은 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단서를 찾아내는 것이다.

예를 들어, [ PRETTY, GIRL, REPEAT ] 와 같은 단어들을 (b), (c), (d)와 같이 찾을 수 있다.

각 글자들은 대각선으로도 이어질 수 있으며, 한 글자가 두 번 이상 사용될 수도 있다. 주어진 칸에서 시작해서 특정 단어를 찾을 수 있는지 확인하는 문제를 풀어보자.

hasWord(y, x, word) = 보글 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부를 반환한다.

 

고민하기

이 문제를 풀 때 까다로운 점은 다른 글자가 될 수 있는 칸이 여러 개 있을 때, 이 중 어느 글자를 선택해야 할지 미리 알 수 없다는 것이다.

만약 (e) 그림의 가운데 칸에서 시작하는 단어 "YES"를 찾고 싶다고 하자.

"Y" 주변의 8칸에 모두 "E"가 들어 있지만 이중 "YES" 로 연결되는 "E"는 하나 뿐이며, "E"만 살펴본다면 어느 "E"를 따라가야 답을 찾을 수 있는지 알 수 없다.

-> 완전 탐색을 이용해, 단어를 찾아낼 때 까지 모든 인접한 칸을 하나씩 확인하는 것이 어떨까?

 

풀이

hasWord()가 하는 일은 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다.

함수를 호출할 때 단어의 시작 위치를 정해주기 때문에, 문제의 조각 중 첫 번째 글자에 해당하는 조각을 간단히 해결할 수 있다.

- 시작 위치에 쓰여 있는 글자가 단어의 첫 글자와 다르다면 바로 false를 반환하고 종료하면 된다.

- 그리고 나서 원래 단어 word에서 첫 글자를 뗀 단어 word[1..]을 격자에서 찾아야 한다.

- 이를 반복하면 된다. 간단하다.

 

기저 사례의 선택

더 이상 탐색 없이 간단히 답을 낼 수 있는 다음 경우들을 기저 사례로 선택한다.

1. 위치 (y, x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패

2. (1번 경우에 해당되지 않을 경우) 원하는 단어가 한 글자인 경우 항상 성공

 

구현

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

 

const int dx[8] = { -1, -1, -1,  1,  1,  1,  0,  0 };
const int dx[8] = { -1,  0,  1, -1,  0,  1, -1,  1 };
// 5*5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는지를 반환
bool hasWord(int y, int x, const string& word) {
	// 기저 사례 1 : 시작 위치가 범위 밖이면 무조건 실패
	if (!inRange(y, x)) return false;
	// 기저 사례 2 : 첫 글자가 일치하지 않으면 실패
	if (board[y][x] != word[0]) return false;
	// 기저 사례 3 : 단어 길이가 1이면 성공
	if (word.size() == 1) return true;
	// 인접한 여덟 칸을 검사한다.
	for (int direction = 0; direction < 8; ++direction) {
		int nextY = y + dy[direction], nextX = x + dx[direction];
		// 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
		if (hasWord(nextY, nextX, word.substr(1)))
			return true;
	}
	return false;
}

 

함수안에서 하나의 문자만 확인하고, 나머지는 다시 hasWord(자기자신)을 호출하여 나머지를 확인한다.

+ 상대좌표를 별도의 변수로 분리해 낸 것도 참고하자.

 

시간 복잡도 분석

완전 탐색 알고리즘의 시간 복잡도를 계산하는 것은 단순하다. 완전 탐색은 가능한 답 후보들을 모두 만들어 보기 때문에, 시간 복잡도를 계산하기 위해서는 가능한 후보의 수를 전부 세어 보면 된다.

-> O(8^N)