재귀란(recursion)?
어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 떄 재귀적(recursive)이라고 합니다. 반복적(iterative)와 같은 말입니다.
재귀의 요소
-
재귀 케이스
차후의 재귀호출은 작아진 부문제들(subproblems)을 대상으로 이루어집니다. -
베이스 케이스
부문제들이 충분히 작이지면, 알고리즘은 재귀를 사용하지 않고 이들을 직접 해결합니다. 베이스 케이스는 중단 조건과 같으며, 반드시 베이스 케이스를 가져야합니다. 재귀호출은 항상 베이스 케이스를 향하는 방향으로 설정하여야 합니다.
int sum(int n) {
if(n == 1) // base case
return 1;
else // recursion
return n + sum(n - 1)
}재귀와 반복문의 비교
반복문으로 순차곱셈 값을 구하는 방법과 재귀 알고리즘의 대표적인 순차곱셈 값을 구하는 비교해봅시다.
반복문 이용
#pragma warning (disable:4996)
#include <stdio.h>
/* 정수 n의 순차곱셈 값을 반환 */
int factorial(int n) {
int result = 1;
for (int i = n; i > 1; i--) // n + 1번 반복
result *= i;
return result;
}
int main() {
int x;
printf("정수를 입력하시오. : ");
scanf("%d", &x);
printf("%d의 순차곱셈 결과는 %d 입니다.", x, factorial(x));
return 0;
}반복문의 시간복잡도는 O(n + 1)이며 변수는 2개 입니다.
재귀 이용
#include <stdio.h>
/* 정수 n의 순차곱셈 값을 반환 */
int factorial(int n) { // n + 1번 반복
if (n > 0)
return n * factorial(n - 1);
else
return 1;
}
int main() {
int x;
printf("정수를 입력하시오. : ");
scanf("%d", &x);
printf("%d의 순차곱셈 결과는 %d 입니다.", x, factorial(x));
return 0;
}
이와 같은 알고리즘 함수 호출 방식은 재귀적 호출(recursive call) 방식 이라고 합니다. 자기 자신과 똑같은 함수를 호출하여 결과를 도출합니다.
- 호출 과정
- 3 입력 factorial(3) 실행
- 3 * factorial(2) 반환 및 factorial(2) 호출
- 2 * factorial(1) 반환 및 factorial(1) 호출
- 1 * factorial(0) 반환 및 factorial(0) 호출
- n == 0이 되므로 1 반환
- 반환값 도출 과정
- 1 반환
- 1 * factorial(0) : (1 * 1) 반환
- 2 * factorial(1) : (2 * 1) 반환
- 3 * factorial(2) : (3 * 2) 반환
- 최종 반환값
6 반환 후 출력
위와 같이 반환값 도출 과정은 역순입니다.
재귀함수도 반복문과 같이 시간복잡도는 O(n + 1)이며, 변수의 개수는 하나가 더 적습니다.
factorial 함수는 그 내부에서 factorial 함수를 호출합니다. 이처럼 자신과 같은 함수를 호출하면 직접(direct)재귀입니다. 간접(indirect)재귀는 함수 a가 함수 b를 호출하고 다시 함수 b가 함수 a를 호출하는 구조로 이루어집니다.
직접재귀 : a() -> a()
간접재귀 : a() -> b() -> a()
유클리드 호제법
유클리드 호제법을 사용한 예로 두 정수의 최대공약수를 재귀적으로 구하는 방법에 대해서 알아보겠습니다.
Q. 크기가 22 * 8인 직사각형을 정사각형으로 완전히 채웁니다. 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하세요.
1번
22 * 8 크기의 직사각형에서 짧은 변(8)을 한 변으로 하는 정사각형으로 분할합니다. 이렇게 하면 8 * 8 크기의 정사각형이 2개가 생기고 6 * 8 크기의 직사각형이 1개 생깁니다.
2번
6 * 8 크기의 직사각형에서 짧은 변(6)을 한 변으로 하는 정사각형으로 분할합니다.
이렇게 하면 6 * 6 크기의 정사각형이 1개가 생기고 6 * 2 크기의 직사각형이 1개 생깁니다.
3번
6 * 2 크기의 직사각형에서 짧은 변(2)을 한 변으로 하는 정사각형을 분할합니다.
이렇게 하면 2 * 2 크기의 정사각형이 3개가 생깁니다.
4번
변의 길이가 2인 정사각형으로 나누어 떨어지므로 최대공약수는 2입니다.
이렇게 두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어떨어지는 가장 큰 값이 최대공약수입니다. 나누어떨어지지 않으면 작은 값(얻은 나머지)에 대해 나우어 떨어질떄까지 같은 과정을 재귀적으로 반복합니다.
먼저 반복문으로 짠 코드부터 살펴봅시다.
#include <stdio.h>
/* 정수 x, y의 최대공약수를 반환 */
int gcd(int x, int y) {
int tmp;
while (y != 0) { // 나누어 떨어질때 종료
tmp = y; // tmp에 작은 값 저장
y = x % y; // y에 나눈 나머지 저장
x = tmp; // x에 전 y값 저장
}
return x; // 처음 나누어 떨어질때 값 반환
}
int main() {
int x, y;
puts("두 정수의 최대공약수를 구합니다.");
printf("정수를 입력하시오. : ");
scanf("%d", &x);
printf("정수를 입력하시오. : ");
scanf("%d", &y);
printf("최대공약수는 %d 입니다.", gcd(x, y));
return 0;
}변수는 3개가 쓰이고 최대공약수를 찾을때까지 반복합니다.
유클리드 호제법을 사용한 코드입니다.
#include <stdio.h>
/* 정수 x, y의 최대공약수를 반환 */
int gcd(int x, int y) {
if (y == 0) // 나누어 떨어질때 최대공약수(x) 반환
return x;
else
return gcd(y, x % y); // gcd(작은 수, 나눈 나머지)
}
int main() {
int x, y;
puts("두 정수의 최대공약수를 구합니다.");
printf("정수를 입력하시오. : ");
scanf("%d", &x);
printf("정수를 입력하시오. : ");
scanf("%d", &y);
printf("최대공약수는 %d 입니다.", gcd(x, y));
return 0;
}변수는 2개가 쓰이고 최대공약수를 찾을때까지 반복합니다. 시간복잡도는 위의 반복문을 쓸때와 같습니다.
다음은 반복문으로 구현하기 복잡한 문제를 다뤄봅시다.
Q. 배열 a의 모든 요소의 최대공약수를 구하는 다음 함수를 작성하세요.
int gcd_array(const int a[], int n)
유클리드 호제법을 이용하여 위의 함수와 같이 구현하였습니다.
#include <stdio.h>
int i = 1;
/* 정수 x, y의 최대공약수를 반환 */
int gcd(int x, int y) {
if (y == 0) {// 나누어 떨어질때 최대공약수(x) 반환
printf("%d번째로 찾은 최대공약수 %d\n", i, x);
i++;
return x;
}
else
return gcd(y, x % y); // gcd(작은 수, 나눈 나머지)
}
//*--- 요솟수 n인 배열 a의 모든 요소의 최대 공약수를 구합니다. ---*/
int gcd_array(const int a[], int n) {
if (n == 1)
return (a[0]);
else if (n == 2)
return (gcd(a[0], a[1]));
else
return (gcd(a[0], gcd_array(&a[1], n - 1)));
}
int main() {
int n, x[100] = { 0 };
printf("요소수 : ");
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &x[i]);
printf("최대공약수는 %d 입니다.", gcd_array(x, n));
return 0;
}일단 출력문 부터 보겠습니다.
n = 5로, 배열값은 차례대로 5 25 50 100 200을 입력하였습니다.
전역변수와 gcd() 함수에서 printf("%d번째로 찾은 최대공약수 %d\n", i, x);를 추가하여 먼저 찾은 최대공약수부터 출력하여 반환 순서를 볼수 있도록 구현하였습니다.
보시면 끝에서 부터 한쌍씩 최대공약수를 구하여 왼쪽으로 이동하면서 최대공약수를 구하는 것을 볼 수 있습니다.
배열 요소가 3개 이상일때, return (gcd(a[0], gcd_array(&a[1], n - 1)));을 보면 a[1]의 주소를 반환해주어 한칸씩 뒤로 미뤄줍니다. n이 2일때까지 이동하여 맨 끝 한쌍의 수에 대해서 최대공약수를 먼저 구해주고, 다시 앞으로 이동하며 최대공약수와 요소수에 대해서 최대공약수를 갱신하며 도출합니다.
재귀함수를 왜쓸까? 어떨때 써야 할까?
- 재귀함수는 반복문과 비교했을때 변수 사용이 줄여줍니다. 그러면 오류가 상대적으로 덜 발생합니다.
- 3, 4...n중 반복문을 써야한다면 굉장히 복잡해지므로 재귀함수를 구현하는게 수월합니다.
- 알고리즘 표현이 자연스러울때 가독성이 좋아집니다.
재귀함수의 단점
- 함수를 반복적으로 호출하면서 스택에 데이터가 축저되 스택오버플로우 현상이 발생할 수 있으며 저장/복구 성능이 저하된다.
- 꼭 필요할때 사용하도록 유의 해야한다.
