1. 재귀(recursion)란?
1. 자기 자신을 호출하며
2. 갈수록 더 작은 문제를 풀게 한다.
3. 그러다가 결국 basic case에 수렴하게 되는 것이다.
2. 팩토리얼
팩토리얼으로 재귀함수에 대해 감을 잡아보자.
4! = 4 * 3 * 2 * 1 이다.
그런데 이것을 4! = 4 * 3! 으로 나타낼 수 있고,
3!은 다시 3 * 2!
2!은 2 * 1!이다.
이것을 코드로 나타내보면 다음과 같다.
#include <iostream>
using namespace std;
int fact(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * fact(n - 1);
}
}
int main() {
cout << fact(4);
return 0;
}
위의 코드로 순환 알고리즘의 구조를 알아보자.
팩토리얼의 규칙은 다음과 같다.
0! = 1
1! = 1
2! = 2*1!
3! = 3*2!
...
n! = n*(n-1)!
위의 두 줄은, 기본적인 조건인 basic case며, 재귀 호출을 멈추는 부분이기도 하다.
아래의 줄들은 재귀 호출을 반복하는 부분이다.
이번에는, 위의 코드를 반복문으로 바꿔보자.
#include <iostream>
using namespace std;
int main() {
int fact = 1;
for (int i = 4; i > 0; i--) {
fact *= i;
}
cout << fact;
return 0;
}
일반적으로, 재귀 알고리즘은 반복 알고리즘으로도 표현 가능하다.
두 알고리즘의 시간 복잡도는 어떻게 될까?
반복 알고리즘은 for를 사용하여 n번 반복하므로 시간 복잡도가 O(n)이다.
재귀 알고리즘은 한번 호출 될 때마다 1번의 곱셈이 수행되고 n번 호출이 일어나므로 역시 시간복잡도가 O(n)이다.
이 둘은 시간복잡도가 같으나, 다른 여러가지 특성에서 다르기 때문에 경우에 따라 재귀 알고리즘과 반복 알고리즘을 적절히 사용해야 한다. 그렇다면, 둘에는 어떤 차이가 있을까?
3. 재귀 vs 반복
"재귀"
- 수학적 방법을 그대로 반영해 수식 세우기가 쉽다.
- 부가적 요소들이 stack에 쌓인다. -> 메모리 용량 잡아먹음.
- 무한 재귀되면 메모리 용량이 초과되어 스택 오버플로우가 발생한다.
"반복"
- 각 반복에 부가공간이 필요하지 않다.
- 무한 반복 시 추가메모리가 필요하지 않고 그냥 쭉 반복된다.
- 재귀 알고리즘에 비해 생각하기가 어렵다.
4. 하노이의 탑
* 하노이의 탑 규칙
- 한번에 하나의 원반만 옮길수 있음
- 옮길 때마다 한 막대의 맨 위의 원반을 다른 막대에 이미 놓여 있는 원반 위로 옮기게 됨.
- 자기보다 작은 원반 위로는 옮길 수 있음.
* 하노이의 탑 알고리즘
< recursion case >
1. n-1개를 C로 옮긴다.
2. 제일 긴 애를 B로 옮긴다.
3. C로 옮겼던 n-1개를 B로 옮긴다.
< Basic case >
막대기가 하나뿐일때,
바로 B로 옮긴다.
Code
#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to) {
if (n == 1) {
// from에 있는 한개의 원판을 to로 옮긴다.
printf("원판 1을 %c에서 %c으로 옮긴다. \n", from, to);
} else {
// from에 있는 n-1개의 원판을 tmp로 옮긴다.
hanoi_tower(n - 1, from, to, tmp);
printf("원판 %d을 %c에서 %c으로 옮긴다. \n", n, from, to);
// tmp에 있는 n-1개의 원판을 to로 옮긴다.
hanoi_tower(n - 1, tmp, from, to);
}
}
int main(void) {
hanoi_tower(4, 'A', 'B', 'C');
return 0;
}
실행 결과
5. 피보나치 수열
< recursion case >
f(n) = F(n-1) + F(n-2) (n>1)
< Basic case >
n == 0일 때, 0
n == 1일 때, 1
* 재귀 알고리즘으로 구현
int fibo_recursion(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibo_recursion(n - 1) + fibo_recursion(n - 2);
}
}
* 반복 알고리즘으로 구현
int fibo_reiteration(int n) {
long long* fibo = new long long[n + 1];
fibo[0] = 0;
fibo[1] = 1;
for (int i = 2; i < n + 1; i++) {
fibo[i] = fibo[i - 1] + fibo[i - 2];
}
return fibo[n];
}
* 전체 코드
#include <iostream>
using namespace std;
int fibo_recursion(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibo_recursion(n - 1) + fibo_recursion(n - 2);
}
}
int fibo_reiteration(int n) {
long long* fibo = new long long[n + 1];
fibo[0] = 0;
fibo[1] = 1;
for (int i = 2; i < n + 1; i++) {
fibo[i] = fibo[i - 1] + fibo[i - 2];
}
return fibo[n];
}
int main() {
int n;
cin >> n;
cout << fibo_recursion(n) << '\n';
cout << fibo_reiteration(n);
return 0;
}
* 실행결과
6. 실습 문제
- factorial 프로그램을 재귀, 반복으로 각각 구현하고 입력 값인 n을 증가시키면서 실행시간을 측정해 화면에 출력되게 실행
- 재귀의 경우, n이 증가함에 따라 어느 정도의 n에서까지는 수행되나, 어느 정도 이후에는 stack overflow로 수행이 안됨을 보이시오.
- 반복의 경우, 위의 재귀를 수행한 n값 부분에서도 수행이 됨을 보이고, 그보다 큰 n값에서도 상당 기간 수행됨을 보이시오.
- 피보나치 수열에 대한 프로그램도 반복과 재귀를 각각 사용해 구현하고 비슷한 실행을 수행하시오.
