재귀함수(1): 재귀함수의 기본

1. 재귀함수란?

재귀함수란 함수 내에서 같은 함수(자기 자신)가 또 실행되는 함수의 형태를 말한다.

가장 기본적인 형태는 base case와 recursive case 둘을 갖는 형태인데, 가장 유명한 예시인 팩토리얼 구하기를 살펴보자.

int fac1(int n) {
	// base case
	if (n <= 1) return 1;

	// recursive case
	return n * fac1(n - 1);
}

(편의상 음수일 때는 무시하자)

이렇게 쉬울 수도 없다. n이 1이하일 때는 1을 그대로 반환하고 2 이상이이면 n * (n-1)!을 반환한다.

사실 이 예시는 굳이 재귀함수를 이용할 필요는 없다. 이렇게 해도 같은 결과를 반환한다.

int fac2(int n) {
	int p = 1;
	for (int i = 2; i <= n; ++i) p *= i;

	return p;
}

심지어 속도도 후자가 더 빠르다.

재귀함수를 사용하면 함수를 계속 호출해야되기 때문에 매개변수에 따른 스택이 쌓이고, 결과값을 전달하고 하는 과정이 있기 때문에 훨씬 느릴 수밖에 없다.

비교를 위해 int가 허용하는 범위에서 최대치인 13! (=1932053504)를 1000만번씩 구하며 그 시간을 비교해보았다.

당연하게도 재귀함수를 사용하지 않은 쪽이 6배 정도 더 빨랐다.

그리고 사실, 모든 코드는 재귀함수를 사용하지 않아도 작성할 수 있다.

그렇다면 우리는 왜 더 느린 재귀함수를 써야 할까?

2. 재귀함수의 필요성

재귀함수의 존재 가치는 크게 두 가지에 있다고 생각한다.

(1) 코드가 간결해진다

재귀함수를 사용하면 코드의 길이를 크게 줄일 수 있다. 컴퓨팅 파워가 많이 증가하고 있는 현재 시점에서, 이는 대단한 장점이 아닐 수 없다.

(2) 코드가 직관적으로 변한다

재귀함수를 사용하면 전체 코드의 흐름을 보다 직관적으로 파악할 수 있다.

프로그래밍을 하는 사람이라면 전체 코드의 흐름은 파악하고 있어야 한다. 이 때 재귀함수는 코드의 흐름을 파악하는 데에 큰 도움을 줄 수 있다.

간단한 예시를 통해 살펴보자.

여기 아주 간단한 형태의 점화식이 있다.

$a_0 = 1, \; a_n = 3a_{n-1} + 2$

이 점화식의 n번째 항을 구하기 위한 코드를 작성해보자.

i) 재귀함수를 사용하지 않았을 때

int rec1(int n) {
	int p = 1;
	for (int i = 0; i < n; ++i) {
		p *= 3;
		p += 2;
	}
	return p;
}

ii) 재귀함수를 사용했을 때

int rec2(int n) {
	if (n == 0) return 1;
	return 3 * rec2(n - 1) + 2;
}

길이도 길이지만, 코드가 한눈에 봐도 훨씬 더 직관적이라는 것을 알 수 있다.

사실 이 예시는 그렇게 복잡하지 않으므로, 재귀함수의 필요성이 잘 와닿지 않을 수도 있다.

나같아도 이 정도 차이면 재귀함수를 사용하지 않고, 더 빠른 속도를 선택할 것 같다.

다음 글부터는 보다 복잡한 예제들을 풀어볼 것인데, 그 과정에서 재귀함수의 가치를 느낄 수 있길 바란다.