[Algorithm] 재귀 함수 (Recursive Function)

개인적으로 Recursive 함수를 많이 사용하는 편이라고 생각했다. 하지만, 항상 사용만 했지 한 번도 제대로 이해해 보려고 했던 적은 없는 것 같다. “프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략” 책을 읽으면서 for Loop과 Recursive 함수를 같이 사용하여 가능한 모든 조합의 수를 찾는 방법을 아주 쉽게 구현할 수 있어서 짧게 정리해보았다. 아래 코드는 책에서 작성된 Pseudocode 코드를 C로 다시 작성한 코드이다. 아래 코드는 PICNIC이라는 문제를 풀기 위한 코드이다. 문제는 서로 친하다고 생각하는 학생들만 짝을 지어 줄 때 가능한 학생의 조합을 찾는 문제이다. 아래 출처 1에서 관련 문제를 확인 할 수 있다.

#define NumStudent 10

#define True 1
#define False 0

int totalStudent;
int relationship[NumStudent][NumStudent];
int studentList[NumStudent];

int numPossibleGroup() {
	//MK: 총 가능한 Combination 수
	int returnValue = 0;
	int firstStudent = -1;
	//MK: 가장 앞 순서 부터 검색을 하기 위해서 제일 처음 가능한 학생 찾기
	for (int i = 0; i < totalStudent; i++) {
		if (studentList[i] == False) {
			firstStudent = i;
			break;
		}
	}
	//MK: 모든 학생이 친구를 찾았기 때문에 함수 종료
	if (firstStudent == -1) { return True; }
	//MK: 모든 가능한 Combination을 찾기 위해 Recursive 함수 호출
	for (int i = firstStudent + 1; i < totalStudent; i++) {
		if (studentList[i] == False && relationship[firstStudent][i] == True) {
			//MK: 짝이 된 친구들을 표시함
			studentList[i] = True;
			studentList[firstStudent] = True;
			//MK: Recursive 함수 호출
			returnValue += numPossibleGroup();
			//MK: 짝이 된 친구들을 Free하고 다시 가능한 combination 검색
			studentList[i] = False;
			studentList[firstStudent] = False;
		}
	}
	return returnValue;
}

numPossibleGroup() 함수는 List의 True, False 값을 이용하여 모든 가능한 조합의 수를 찾는 함수이다. numPossibleGroup() 함수 안의 for Loop은 현재의 가능한 Sub-Combination을 찾기 위해서 현재 짝이 된 2학생 (List Index)의 값에 True로 설정한다. 그리고 현재 짝이 된 학생을 제외한 모든 가능한 조합의 수를 찾기 위해 다시 numPossibleGroup() 함수를 호출한다. 이 부분에서 Recursive 함수가 된다. 현재 짝이 된 학생을 제외한 모든 조합의 수를 찾은 후 현재 함수로 다시 돌아오면, 처음에 짝이 된 2학생 (List Index)의 값을 다시 False로 세팅한다. 그리고 다시 새로운 짝을 찾아서 조합을 계속 계산하다.

그림 1: Recursive 함수 동작 순서 정리 

위 그림은 numPossibleGroup() 함수가 호출되는 순서를 정리해보았다. List (학생 번호)의 값이 0이면 False이고, List 값이 1이면 True이다. True는 해당 학생이 짝을 찾았다는 의미이다. 위 예제는 모든 학생이 친구가 될 수 있다고 가정을 한 경우이다.

순서 설명

  1. 가장 먼저 #0과 #1학생이 짝이 된다. (Func #1)
  2. 그리고 새로운 numPossibleGroup() 함수를 호출한다. (Func #2)
  3. Func #2에서 #2와 #3학생이 짝이 된다.
  4. 다시 새로운 numPossibleGroup() 함수를 호출한다. (Func #3)
  5. Func #3에서 #5와 #6학생이 짝이 된다. 모든 가능한 조합의 수를 찾았기 때문에 함수를 종료한다. 실제로 여기서 numPossibleGroup() 함수를 한 번 더 호출한다. 다음 호출된 함수의 if (firstStudent == -1) { return True; } 라인에서 종료되어서 현재 함수로 돌아온다.
  6. Func #3에서 #5와 #6학생이 짝을 다시 헤어지게 한다. 해당 학생 번호에 False로 값으로 Reset 한다. (Func #3 종료)
  7. Func #2에서 #2와 #3학생들이 짝이 되지 않은 경우를 탐색하기 위해 #2와 #3의 Reset 한다.
  8. Func #2에서 #2와 #4학생이 짝이 된다.
  9. 다시 새로운 numPossibleGroup() 함수를 호출하여 가능한 조합을 다시 탐색한다.

위의 순서대로 계속 반복을 하다 보면 모든 가능한 조합의 수를 찾게 된다. 위 코드는 중복되는 경우의 수를 제거하기 위해서 절대로 앞 번호를 가진 학생과는 짝이 될 수 없도록 작성하였다. numPossibleGroup()을 호출하기 전에 List의 True, False를 사용하는 모든 가능한 조합의 수를 찾는 방법을 알지 못하였던 부분이라 간단하게 정리해보았다.

출처

  1. https://algospot.com/judge/problem/read/PICNIC
  2. 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 (구종만)

Leave a Comment