[자료구조] 재귀(recursion)

재귀는 함수가 자기 자신을 호출할 때를 말하는 공식 명칭이다. 일반적으로 무한 함수 호출은 쓸모가 없고 위험하기까지 하지만 재귀는 활동 가능성이 큰 강력한 도구다. 

 

10에서 0까지 카운트 다운하는 함수를 만들어 보자.

#include <iostream>
using namespace std;

void countdown(int number)
{
	for (int i = number; i >= 0; i--)
		cout << i << endl;
}

int main()
{
	countdown(10);
	return 0;
}

구현에는 문제가 없지만 루프가 필요 없었을 수도 있다. 루프 대신 재귀를 사용해 보자.

#include <iostream>
using namespace std;

void countdown(int number)
{
	if (number < 0)
		return;
	cout << number << endl;
	countdown(--number);
}

int main()
{
	countdown(10);
	return 0;
}

countdown을 처리하는 위와 같은 예제는 재귀로 풀 수 있지만, 전형적인 루프로도 쉽게 풀 수 있다. 재귀가 흥미롭긴 하지만 이러한 문제를 푸는 데 있어 사실상 이점은 없다. 하지만 재귀는 한 알고리즘 내에 같은 알고리즘을 반복해야 하는 상황과 자연스럽게 들어맞는다. 이럴 때 재귀를 사용하면 보다 읽기 쉬운 코드로 만들 수 있다.

 

주어진 디렉터리의 하위 디렉터리를 출력하는 함수를 만들어 보자. (C++17부터는 filesystem을 이용하자)

#include <iostream>
#include <io.h>
using namespace std;

void searchDirectory(string path)
{
	string dirPath = path + "\\*.*";
	struct _finddata_t fd;
	intptr_t handle = _findfirst(dirPath.c_str(), &fd);
	if (handle == -1L)
	{
		return;
	}

	int checkDirfile = 0;

	do
	{
		if (!(fd.attrib & _A_SUBDIR)) // 디렉터리가 아니면 continue
			continue;
		if (fd.name[0] == '.') // ".", ".." continue
			continue;

		cout << path << "\\" << fd.name << endl;
		searchDirectory(path + "\\" + fd.name); // 하위 디렉터리 검색

	} while (_findnext(handle, &fd) == 0);
	_findclose(handle);
}

int main()
{
	searchDirectory("D:\\새폴더");
	return 0;
}

위의 예제처럼 알고리즘 자체만으로는 얼마나 많은 깊이를 들어가야 하는지 알 수 없을 때 재귀는 좋은 방법일 수 있다.