순환
개념
- 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
- 정의 자체가 순환적으로 되어 있는 경우 적합
프로그램에서 되풀이 해결방법
순환(recursion)- 순환적인 문제에서는 자연스러움
- 함수 호출에 오버헤드 발생 가능성
반복(iteration)- 수행속도가 빠름
- 순환적인 문제에 관해서는 프로그램 작성이 어려워질 수도 있음
팩토리얼
순환(Recursive) 구현
int factorial_recur(int x)
{
if(x == 1) return 1; // 순환 비호출 부분
return x*factorial_recur(x-1); // 순환 호출 부분
}
반복(Iter) 방식 구현
int factorial_iter(int x){
if(x == 1) return 1;
int result = 1;
for(int i = x; i >= 1; i--){
result *= i;
}
return result;
}
시간복잡도 비교
- 순환 방식 : O(n)
- 반복 방식 : O(n)
거듭제곱값 계산
순환(Recursive) 구현
int power_recur(int x,int n)
{
if(n == 0) return 1;
if(n % 2 == 0){
return power_recur(x*x,n/2);
}
else return x*power_recur(x*x,(n-1)/2);
}
반복(Iter) 방식 구현
int power_iter(int x,int n)
{
if(n == 0) return 1;
int result = 1;
for(int i = n; i >= 1; i--){
result *= x;
}
return result;
}
시간복잡도 비교
- 순환 방식 : O(logN) ← N = 1024라면 x^1024 → x^512 → x^256 … → x^4 → x^2 → x^1
- 반복 방식 : O(n)
- 순환 방식이 더 빠를 수도 있다.
피보나치수열
순환(Recursive) 구현
int fib_recur(int n)
{
if(n == 0) return 0;
if(n == 1) return 1;
return fib(n-1) + fib(n-2);
}
반복(Iter) 방식 구현
int fib_iter(int n)
{
if(n == 0) return 0;
if(n == 1) return 1;
int pre = 0;
int cnt = 1;
int result = 0;
for(int i = 2; i <= n; i++){
result = pre + cnt;
pre = cnt;
cnt = result;
}
return result;
}
순환 호출 사용 시 비효율성 발생
- 피보나치수열 함수를 fib(N)이라고 할 때 fib(6) 계산을 도식화
순환적 피보나치수열 시간 복잡도 계산
- 이런 중복 현상은 n이 커지면서 더 심해짐
→ 시간 낭비 커짐 - 피보나치수열은 반복 방식이 더 효율적
반복 방식 시간 복잡도 : O(n)
하노이 탑 문제
- 3개의 막대 A, B, C / 서로 다른 크기의 원판 n개
- 문제 : 막대 A에 있는 쌓여있는 원판 n개를 막대 C로 옮기는 것
- 조건
- 한 번에 하나의 원판만 이동 가능
- 맨 위에 있는 원판만 이동 가능
- 크기가 작은 원판 위에 큰 원판 쌓을 수 없음
- 중간의 막대를 임시 사용 가능, 하지만 앞의 조건을 지켜야 함
- 예시 (n = 3)
- 일반적인 접근법을 이용한 순환적 알고리즘 n개의 원판을 C 막대로 옮기는 것을
일반적으로 푼다면 이런 식으로 푸는 것이 가장 간단
- 원판을 두 그룹으로 나눈다. 1개(빨간색)와 n-1개(파란색)
1. 파란색 그룹을 B막대로 옮긴다.
2. 빨간색을 C막대에 옮긴다
3. 파란색 그룹을 C막대에 옮기면 끝
이를 하노이 문제의 조건을 적용시킬 수 있을까? 가능하다.
어떻게? 원판의 그룹을 계속계속 나눠주면 된다.
그러면 1개가 남을 때까지 계속될 것이다.
즉 해당 로직을 함수라고 쳤을 때 이를 재귀함수로 호출해 주면 된다는 소리이다.
하노이 순환적 알고리즘 유사코드 및 구현
- 유사코드
// 막대 from에 쌓여있는 n개의 원판을 막대 tmp를 사용해 막대 to로 옮긴다.
void hanoi(int n, char from, char tmp, char to)
{
if(n == 1) from에서 to로 옮긴다.
else{
(1) hanoi(n-1,from,to,tmp)
(2) from에 있는 하나 남은 원판을 to로 옮긴다.
(3) hanoi(n-1,tmp,from,to)
}
}
- 구현
void hanoi(int n, char from, char tmp, char to)
{
if(n == 1) printf("원판 1을 %c에서 %c로 옮긴다\\",from,to);
else{
hanoi(n-1,from,to,tmp);
printf("원판 %d를 %c에서 %c로 옮긴다\n",n,from,to);
hanoi(n-1,tmp,from,to);
}
}
알아두면 좋은 관련 지식 및 문제
- 팩토리얼 계산하는 순환 호출에서 매개변수로 5가 주어졌을 때 최대 활성 레코드 수는?
- 5가 4를 호출, 4가 3을 호출, 3이 2를 호출, 2가 1을 호출, 1부터는 종료
- 5,4,3,2,1 → 최대 5개
- 활성 레코드에 저장되는 것 → 매개변수 값, 함수호출 끝나고 복귀 주소, 지역변수
- 해당 함수를 호출하고 “recursive”를 입력한 다음 엔터키를 누르면 출력되는 것은?
void unknown()
{
int ch;
if((ch=getchar()) != '\n')
unknown();
putchar(ch);
}답 : evisrucer ← 간접적으로 스택에 저장되는 것과 비슷하기 때문에 역순으로 호출