16-2-다.디렉토리 검색
재귀 호출이 꼭 필요한 가장 대표적인 예는 디렉토리를 검색할 때이다. 디렉토리안에는 주로 파일이 저장되지만 또 다른 서브 디렉토리가 있을 수 있으며 서브 디렉토리의 개수나 깊이에 특별한 제한이 없다. 파일 시스템은 한 디렉토리안에 임의 깊이로 수천, 수만개의 다른 서브 디렉토리가 존재하는 트리 형태로 되어 있다.
루트 디렉토리 안에 서브 디렉토리가 있고 그 안에는 또 다른 서브 디렉토리가 있다. 루트 디렉토리 안에 서브 디렉토리가 있을 수 있듯이 서브 디렉토리는 또 다른 자식 디렉토리를 가질 수 있으므로 루트 디렉토리의 모양과 서브 디렉토리 하나의 구조가 완전히 일치한다. 위 그림에서 Program 디렉토리만 떼어 놓고 보면 Program 디렉토리가 루트인 작은 트리로 볼 수 있다. 즉 자료 구조가 재귀적이며 이런 디렉토리를 관리하고자 할 때는 재귀 호출이 반드시 필요하다.
다음 예제는 윈도우즈 디렉토리안의 모든 파일을 검색해서 화면으로 출력한다. 검색된 파일의 이름을 printf로 단순히 출력만 했는데 이름을 알고 있으므로 원한다면 복사, 삭제, 이름 변경, 검색 등 어떤 동작이든지 할 수 있다. 특정 디렉토리안에 조건에 맞는 모든 파일에 대해 어떤 작업을 하고 싶다면 이 예제처럼 일단 디렉토리 전체를 순회할 수 있어야 한다.
디렉토리 검색에는 FindFirstFile, FindNextFile 등의 API 함수를 사용했는데 이 함수들과 WIN32_FIND_DATA 구조체에 대해서는 API 서적을 참고하기 바란다. 지금 다루는 주제는 재귀 호출이지 파일 검색이 아니므로 여기서는 이 함수들에 대해 알고 있다고 가정한다. 지금까지 보아오던 짤막한 소스에 비해서 조금 길고 복잡해 보이는데 지역변수가 많을 뿐 개념은 Factorial 예제와 동일하다.
|
예 제 : FileList |
#include <Turboc.h>
void FileList(char *path)
{
HANDLE hSrch;
WIN32_FIND_DATA wfd;
BOOL bResult=TRUE;
char drive[_MAX_DRIVE];
char dir[MAX_PATH];
char newpath[MAX_PATH];
printf("\n검색 경로 = %s\n",path);
hSrch=FindFirstFile(path,&wfd);
if (hSrch == INVALID_HANDLE_VALUE) {
return;
}
_splitpath(path,drive,dir,NULL,NULL);
while (bResult) {
if (wfd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) {
if (strcmp(wfd.cFileName,".") && strcmp(wfd.cFileName,"..")) {
sprintf(newpath,"%s%s%s\\*.*",drive,dir,wfd.cFileName);
FileList(newpath);
}
} else {
printf("%s%s%s\n",drive,dir,wfd.cFileName);
}
bResult=FindNextFile(hSrch,&wfd);
}
FindClose(hSrch);
}
void main()
{
char Path[MAX_PATH];
GetWindowsDirectory(Path,MAX_PATH);
strcat(Path,"\\*.*");
FileList(Path);
}
실행해 보면 엄청난 수의 파일 목록이 스크롤되어 올라갈 것이다. main 함수에서 윈도우즈의 경로를 조사해서 모든 파일을 의미하는 *.* 마스크를 붙인 후 FileList 함수를 호출한다. 윈도우즈 경로는 시스템에 따라 다르지만 통상 C:\Windows라고 할 수 있다. main에서 FileList("C:\Windows\*.*")를 호출함으로써 파일 목록 조사 작업이 시작된다.
FileList 함수는 조건에 맞는 파일을 찾아(이 경우 모든 파일) printf로 파일명을 출력한다. 예를 들어 "부채.bmp" 파일이 발견되었다면 "C:\Windows\부채.bmp" 문자열이 출력될 것이다. 파일 목록을 조사하고 경로를 출력하는 작업은 Windows 디렉토리의 모든 파일을 다 찾을 때까지 while 루프에 의해 반복된다.
만약 파일 검색중에 디렉토리가 발견되면(디렉토리는 DIRECTORY 속성을 가지는 파일의 일종이다.) 이때 재귀 호출이 발생한다. newpath 버퍼에 새로 발견된 디렉토리의 경로를 조립한 후 FileList 함수로 이 경로를 넘겨준다. 예를 들어 System이라는 이름을 가지는 디렉토리가 발견되었다면 FileList("C:\Windows\System\*.*") 함수가 호출될 것이며 새로 호출된 FileList 함수는 System을 루트로 하여 이 디렉토리안의 모든 파일과 서브 디렉토리를 검색할 것이다.
FileList(Windows) 함수가 검색 범위를 조금 좁혀서 FileList(System) 함수를 재귀 호출한 것이다. 스택에는 FileList 함수의 새로운 인스턴스가 생성되며 이 함수의 모든 지역변수가 다시 생성되고 초기화된 후 FileList(System) 함수의 실행이 시작된다. 이때 FileList(Windows) 함수는 FileList(System)을 호출해 놓고 이 함수가 리턴할 때까지 대기하되 검색중의 모든 상황은 자신의 지역변수에 그대로 유지된다.
FileList(System) 함수는 자신의 지역변수로 새로운 검색을 시작하여 System 디렉토리안의 파일 목록을 printf로 출력한다. 검색중에 또 다른 서브 디렉토리 Driver를 발견하면 이때도 똑같은 절차를 거쳐 새로운 FileList(Driver) 함수가 재귀 호출된다. 이때의 호출 스택과 파일이 검색되는 과정을 그림으로 그려 보면 다음과 같다.
FileList(Driver)가 실행중인 동안 앞쪽 두 함수는 스택에 자신의 지역변수를 그대로 간직하고 있는 상태이다. FileList(Driver)가 모든 파일을 검색하면 while 루프를 탈출하여 리턴하며 이때 FileList(System)은 스택에 저장해 둔 지역변수를 꺼내 Driver 디렉토리 이후의 검색을 계속한다. 위 그림의 경우 FileC부터 검색이 재개될 것이다. 만약 Driver 이후에 Config, Setup 등의 서브 디렉토리들이 더 발견되면 동일한 방법으로 재귀 호출이 발생하여 이 디렉토리 안도 검색된다.
System 디렉토리내의 모든 파일이 검색되면 FileList(System) 함수가 리턴되며 이때 FileList(Windows) 함수가 제어를 받아 System 디렉토리 이후를 검색하며 이런 절차로 Windows 디렉토리안의 모든 파일과 서브 디렉토리, 그리고 손자 디렉토리까지 나열되는 것이다. 최종적으로 Windows 디렉토리의 모든 파일이 검색되면 FileList(Windows) 함수가 리턴하며 파일 목록 조사 작업이 끝난다.
이상으로 이 예제의 동작 방식에 대해 설명했는데 다소 복잡하기는 하지만 재귀 호출의 원칙을 일관되게 준수하고 있으므로 개념만 확실하게 파악하고 있으면 이해에 무리는 없을 것 같다. 다음 몇 가지 유의 사항을 생각해 보면서 이 예제와 재귀 호출의 일반적인 특성에 대해 정리해 보자. 예제의 코드를 확실하게 이해했으면 다음 사항들은 쉽게 수긍이 갈 것이다.
① 각 호출 인스턴스의 모든 검색 정보는 함수의 지역변수에 완벽하게 보존된다. 그래서 중간에 재귀 호출이 발생하여 다른 함수를 호출하더라도 작업 경과가 보존되며 재귀 함수가 리턴되면 보존된 정보로부터 다음 검색을 계속할 수 있다. FileList 함수의 hSrch 검색 핸들, 검색 중인 파일의 위치를 가지는 wfd 구조체 등이 모두 지역변수로 선언되어 있기 때문에 각 호출 인스턴스별로 스택에 새로운 변수가 생성되고 각각의 검색 상태가 온전히 보존되는 것이다. 만약 wfd 구조체가 전역으로 선언되어 있다면 FileList 함수는 정확한 재귀 호출을 할 수 없다. 일반적으로 재귀 호출 함수는 전역변수를 읽을 수만 있으며 쓰기는 할 수 없다.
② FileList 함수의 총 호출 회수는 Windows 디렉토리 안의 서브 디렉토리 개수 + 1회이다. 서브 디렉토리 1000개가 있다면 최초 main에서 호출하는 회수 한 번, 각 서브 디렉토리에 대해 한 번씩 호출되어 총 1001번 FileList 함수가 호출될 것이다. 디렉토리 수가 많을수록 호출 회수가 늘어나며 함수를 호출할 때는 오버헤드가 있기 때문에 이 함수의 동작은 상당히 느릴 수밖에 없다. 하지만 하드 디스크가 원래부터 느린 존재이기 때문에 파일 검색은 본질적으로 시간이 걸릴 수밖에 없으므로 반드시 재귀 호출 때문에 느리다고만 할 수는 없다. 따라서 이런 경우는 속도를 위해 굳이 일반 함수로 변환하려고 애쓸 필요가 없다.
③ 최대 중첩 호출 회수는 가장 깊은 디렉토리의 차수만큼이다. 만약 Windows 디렉토리의 서브 디렉토리 중 가장 깊은 디렉토리가 C:\Windows\Temp\IECache\2004\Image\Jpg라면 이 디렉토리의 파일 목록을 조사할 때 스택에 여섯 개의 FileList 호출 인스턴스가 존재하게 된다. 아무리 디렉토리가 많아도 함수가 호출되었다 리턴되었다를 반복하기 때문에 디렉토리의 개수는 중첩 회수와는 직접적인 연관이 없으며 최대 깊이만큼만 중첩된다. 디렉토리는 최악의 경우라도 100단계 이상 중첩되는 경우가 극히 드물기 때문에 이 함수처럼 지역변수가 많더라도 스택 오버플로우는 크게 걱정하지 않아도 된다.
④ FileList 함수는 반환점이 특별히 명시되어 있지 않다. 한 디렉토리안의 파일 검색이 끝나면 자연스럽게 while 루프를 빠져 나오도록 되어 있다. 특정 디렉토리안의 파일과 서브 디렉토리의 총 개수는 무한하지 않으므로 이 함수는 언젠가는 종료될 것이며 그래서 무한 루프에 빠져들지 않는다.
디렉토리같이 트리 구조를 이루는 자료 구조는 아주 흔하다. 윈도우즈의 레지스트리도 트리 구조로 되어 있으며 데이터 베이스 테이블들도 계층적인 구조를 가지는 경우가 많다. 이런 재귀적인 자료 구조를 다룰 때는 일반적인 함수보다 재귀 호출이 훨씬 더 편리하며 간단하다.