[자료구조] 재귀 (recursion)

재귀란?

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다.

 

재귀 함수를 선언할 때 선언한 함수 자신을 호출하는 것입니다. 그렇게 되면 재귀 함수를 한 번 만 실행해도 함수 자신을 호출하므로 또 다시 함수가 실행되고.. 를 계속 반복하는 것이 바로 재귀(recursion)입니다.

 

구글에 재귀를 검색하면 검색어 추천으로 재귀를 추천해주는(!) 이스터에그입니다.

 

재귀의 대표적인 예시가 바로 팩토리얼(factorial) 함수인데, 코드로 살펴봅시다.

int factorial(n) {
	if(n <= 1)	return 1;
	else return n * factorial(n - 1);
}

이렇게 함수의 끝에 선언한 함수 자신을 호출하는데, 이 때 매개변수를 정의한 함수와 다르게 줘서 무한으로 함수가 돌지 않도록 하고 있습니다. 물론 원하는 값을 얻으려는 목적도 있겠지만, 재귀 함수를 작성할 때 주의해야 할 점 1순위는 무한 루프가 빠지지 않도록 작성해야 한다는 것입니다.

 

재귀와 반복문

재귀와 반복문은 반복적으로 명령을 수행하기 위해 만들어진 방법입니다. for 키워드로 반복을 제어하는 변수를 사용해 일정 횟수동안 반복 시킬 수도 있고, while 키워드로 어떤 조건이 만족될 때까지 반복시킬 수도 있습니다.

 

그런 의미에서 재귀와 반복문은 서로 상호관계에 있다고 볼 수 있습니다. 재귀로 적힌 알고리즘을 반복문으로 변경할 수 있고, 반대로 반복문으로 적힌 알고리즘을 재귀로 변경할 수 있습니다.

 

하지만 재귀는 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있습니다. 부가적인 장점과 단점들은 아래 표로 표현했으니 참고하시면 될 것 같습니다.

	재귀 (recursion)	반복문 (while, for, …)
장점	명확하고 간결한 코드	속도가 빠름
단점	메모리를 많이 사용함. 속도가 느림	복잡한 코드

 

예시 1. 거듭제곱값 계산

거듭제곱을 구하는 알고리즘을 만든다고 생각해봅시다. $2^{100}$을 계산하고 싶은데, 단순 반복문으로 계산한다면 2를 100번 곱할 것입니다. 하지만 재귀를 사용하면 100번 곱하지 않아도(일단 자료형은 신경쓰지 맙시다.) 그 수를 구할 수 있습니다.

 

$2^{100}$을 잘 생각해봅시다. 이 숫자는 $(2^2)^{50}$으로 변경할 수 있습니다. 벌써부터 계산해야 할 양이 반으로 줄었네요. 하지만 연산량을 더 줄일 수 있습니다. $2*((2^2)^2)^{24}$로 변경할 수 있겠죠? 이런 식으로 점점 지수를 잘게 쪼개서 $O(log n)$으로 연산량을 대폭 줄일 수 있습니다.

 

지수가

• 짝수라면, 지수를 반으로 나누어 다시 함수를 호출합니다.
• 홀수라면, 같은 수를 곱해서 지수를 짝수로 만든 다음 반으로 나누어 다시 함수를 호출합니다.

같은 수를 곱해서 지수를 짝수로 만든다는게 무슨 말이냐면, 지수가 홀수인 숫자 아무거나 예시로 들어보면

$2^{25}$인 숫자가 있다고 합시다. 우리는 지수를 반 줄이는게 목적인데 지수가 홀수이면 반으로 나누었을 때 소수가 되어버립니다. 그래서 정상적인 계산이 되지 않겠죠? 따라서 같은 수를 곱해서 지수를 짝수로 만든 다음 ($2 * 2^{24}$) 지수를 반으로 나누는 것($2 * (2^2)^{12}$)입니다.

 

 

코드로 표현하면 아래와 같습니다.

double power(double x, int n) {
	if (n == 0) {
		return 1;
	} else if ((n % 2) == 0) {
		return power(x * x, n / 2);
	} else {
		return x * power(x * x, (n - 1) / 2));
	}
}

 

응용: [백준 1629] 곱셈

이를 응용하여 아래와 같은 문제를 풀 수 있습니다. 이 문제는 직접 수를 구하는 것은 아니고, mod 연산(나머지 연산)을 이용해서 한 자릿수만 구하면 되는 문제입니다.

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

해설은 아래와 같습니다.

https://laurent.tistory.com/entry/%EB%B0%B1%EC%A4%80-1629-%EA%B3%B1%EC%85%88-CC

[백준 1629] 곱셈 (C/C++)

 

 

예시 2. 피보나치 수열의 계산

피보나치 수열은 이탈리아 수학자 피보나치(Leonardo Fibonacci)가 발견한 수열입니다. 한 쌍의 토끼가 번식하는 상황을 수열로 만들었다고 합니다.

 

이 수열은 0번째 숫자와 1번째 숫자는 1이라 가정했을 때, $n$번째 숫자는 $n - 1$번째 숫자와 $n-2$번째 숫자의 합으로 수열을 이룹니다.

 

코드로 나타내면 아래와 같습니다.

int fib(int n) {
	if(n == 0) return 0;
	if(n == 1) return 1;
	else return fib(n - 1) + fib(n - 2);
}

 

코드가 정말 직관적이어서 구현하기 매우 쉽지만, 시간 복잡도가 기하급수적으로 증가하는 치명적인 단점을 가지고 있습니다. 이 함수는 시간 복잡도가 $O(2^n)$입니다. $n = 5$일 때 함수를 어떻게 호출하는지 트리로 한 번 보겠습니다.

 

fib(5)를 호출하면 재귀 함수에 의해 연쇄적으로 다수의 함수가 호출됨

$n = 5$인 피보나치 수열을 계산하고 있지만, $n = 3$인 피보나치 수열을 두 번 계산하고 있습니다. 어차피 같은 값이 나오는데 여러 번 계산해서 좋을 것이 없습니다. 따라서 실제로 쓰려면 개선을 한 알고리즘이 필요해보입니다.

 

방법은 의외로 간단합니다. 반복문으로 이전 값들을 저장하면서 피보나치 수열을 구하면 됩니다.

int fib_m (int n) {
	if(n == 0) return 0;
	if(n == 1) return 1;

	// fib(n - 2)
	int n2 = 0;

	// fib(n - 1)
	int n1 = 1;

	// fib(n)
	int res = 0;

	for(int i = 2; i <= n; i++) {
		res = n2 + n1;
		n2 = n1;
		n1 = res;
	}
	return res;
}

 

다른 방법은, 배열에 저장을 하면서 피보나치 수열의 값이 이미 있다면 배열에서 값만 꺼내다 쓰는 방식으로 계산의 양을 줄이는 방법이 있습니다. 이 기법을 메모이제이션(memoization)이라고 하는데, 나중에 기회가 된다면 이에 대해 자세하게 작성해보도록 하겠습니다.

int n, d[50] = { 0, 1 };

int fib(int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (d[n] != 0) return d[n];

	d[n] = fib(n - 2) + fib(n - 1);
	return d[n];
}

 

응용: [백준 2747] 피보나치 수

이를 응용하여 아래와 같은 문제를 풀 수 있습니다. 시간 복잡도에 유의하면 쉽게 풀 수 있는 문제입니다.

https://www.acmicpc.net/problem/2747

2747번: 피보나치 수

 

해설은 아래와 같습니다.

https://laurent.tistory.com/entry/%EB%B0%B1%EC%A4%80-2747-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98-CC

[백준 2747] 피보나치 수 (C/C++)

 

예시 3. 하노이탑 문제

세 개의 막대 중 다른 하나의 막대로 원판을 모두 옮기는 문제입니다. 고대 인도의 신이 승려에게 64개의 원판을 크기가 큰 것부터 차례대로 쌓아놓은 것을 다른 막대기로 옮기라고 했다는 전설에서 시작되는 문제입니다.

이 문제에서는 아래의 조건에 맞게 원판을 옮겨야 합니다.

• 한 번에 하나의 원판만 옮길 수 있음
• 맨 위에 있는 원판만 옮길 수 있음
• 크기가 작은 원판 위에 큰 원판이 쌓일 수 없음
• 중간의 막대를 임시적으로 이용할 수 있으나 위의 조건들을 지켜야 함

from -> via -> to

원판을 from에서 via를 거쳐 to까지 옮긴다고 해봅시다.

1. $n$개의 원판이 from에 쌓여있습니다. 먼저, 위에 쌓여있는 $n - 1$개의 원판을 via로 옮깁니다.
2. 그럼 from에 제일 밑에 있던 1개의 원판이 남을겁니다. 이 원판을 to로 옮깁니다.
3. via에 있는 $n - 1$개의 원판을 to로 옮깁니다.

 

코드로 나타내면 다음과 같습니다.

void hanoi(char from, char via, char to, int n) {
	if (n == 1) {
		printf("원판 1을 %c에서 %c로 옮긴다.\\n", from, to);
	} else {
		// 원판의 n - 1개를 from -> via (to는 경유)로 옮김
		hanoi(from, to, via, n - 1);
		printf("원판 %d을(를) %c에서 %c(으)로 옮긴다.\\n", n, from, to);
		// 원판의 n - 1개를 via -> to (from은 경유)로 옮김
		hanoi(via, from, to, n - 1);
	}
}

 

응용: [백준 11729] 하노이 탑 이동 순서

이를 응용하여 아래와 같은 문제를 풀 수 있습니다.

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

해설은 아래와 같습니다.

https://laurent.tistory.com/entry/%EB%B0%B1%EC%A4%80-11729-%ED%95%98%EB%85%B8%EC%9D%B4-%ED%83%91-%EC%9D%B4%EB%8F%99-%EC%88%9C%EC%84%9C-CC

[백준 11729] 하노이 탑 이동 순서 (C/C++)