Chapter 02 순환
1. 순환(recursion)
① 순환이란?
알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
정의자체가 순환적으로 되어 있는 경우에 적합한 방법
순환은 함수가 자기 자신을 호출하는 것이다. 함수는 어떤 특별한 일을 하는 명령문의 집합이고 함수 정의(Fuction Definition)는 함수를 작성하는 것을 의미한다. 함수 호출(Fuction Call)은 함수가 실행되기 위한 전제조건이다.
② 팩토리얼 프로그래밍
- 팩토리얼의 정의
int factorial(int n) {
if (n == 0)
return 1;
else
return n * factorial(n-1);
}
리턴하는 데이터형 integer
호출할 때는 함수 이름을 쓴다. factorial(5); 호출시, 5 팩토리얼의 값을 리턴해준다.
함수를 정의하는데 자기자신을 호출하는 부분이 들어가 있는 것 이를 ‘순환함수’라고 한다.
자기자신을 재사용하여 정의하는 것으로, 스스로를 참조한다고 볼 수 있다.
위의 팩토리얼의 바디 부분에서 자기 자신을 호출하는 부분이 나타나는 것 -> ‘순환’
③ 순환호출순서
- 팩토리얼 함수의 호출 순서
factorial(3){
if(3 <= 1) return 1;
else return (3 * factorial(3-1));
}
factorial(2){
if(2 <= 1) return 1;
else return (2 * factorial(2-1));
}
factorial(1){
if(1 <= 1) return 1;
else return (1 * factorial(1-1));
}
(3팩토리얼로부터) 함수를 호출한 다음부터 반환값이 존재한다. 함수를 호출하면 항상 결과값이 온다. 따라서 2팩토리얼이 호출이 되고 2팩토리얼이 실행이 된다. 이후, 다음으로 1팩토리얼이 시작되고 자기를 부르는 값, 1이 리턴이 된다. 이것이 다시 2로 가서 결과값을 3으로 넘겨준다. 이런식으로 실행되는 게 순환이다.
- 출력문이 추가된 순환적 팩토리얼 프로그램
int factorial(int n){
printf("factorial(%d)\n", n);
if( n <= 1 ) return(1);
else return ( n * factorial(n-1) );
}
factorial(3)으로 호출되면, 출력은 다음과 같다.
factorial(3)
factorial(2)
factorial(1)
④ 순환 알고리즘의 구조
만약 순환 호출을 멈추는 부분이 없다면: 시스템 오류가 발생할 때까지 무한정 호출을 하게 된다.
무한히 호출하는 것이 아니라, 언젠가 끝나게끔 제동을 걸어주어야 한다. 언젠가는 끝날 수 있는 구조로 호출을 해야 한다. 따라서 순환을 멈추게 하는 부분을 반드시 포함해야 한다.
1) 다음과 같은 함수를 sub(10)으로 호출하는 경우에 어떤 값이 반환되는가?
int sub(int n)
{
int(n<0)return0;
return n + sub(n-3)
}
sub(10) 호출된 후 다음으로 sub(7), 이후 sub(4) 호출, (모두 리턴되기를 결과를 기다리고 있는 상황), 이후 sub(-1)호출, 여기서 1이 리턴되어 다시 4로 돌아가고 7로 5가 리턴되고 12가 10으로 리턴되어 계산 후, 결과적으로 22가 호출된다.
2) 위의 함수를 반복기법을 이용하여 반복 함수로 다시 작성하시오.
int sub(int n) {
int i;
sum = 0;
for(i = n; i > 0; i = i - 3);
sum = sum + i;
}
⑤ 순환과 반복의 관계
대부분의 순환은 반복으로 바꾸어 작성할 수 있다.
반복문으로 작성할 수 있는데 왜 굳이 순환을 쓸까?
순환이 반복에 비해서 훨씬 효율적일 때가 있고, 순환을 통해 문제가 간단해지는 경우가 분명 존재하기 때문이다. 반복적인 방법으로 굳이 풀어서 쓰는 것이 번거로운 상황이 있다.
2. 거듭제곱 값 프로그래밍 분석
거듭제곱의 경우, 순환적인 방법이 반복적인 방법에 비해 효율적이다.
| 반복적인 거듭제곱 계산 프로그램 | 순환적인 거듭제곱 계산 프로그램 |
double slow_power(double x, int n) { int i; double result = 1.0; for(i=0; i < n; i++) result = result * x; return(result); } |
double slow_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); } |
결론적으로 이야기하면, 반복적인 방법에 비해서 이게 훨씬 효율적이고, 이런 경우는 순환을 써야 한다.
시간 복잡도는 빅오 표기법으로 표기하면 반복적인 방법은 n에 비례하는 것이다.
순환적인 알고리즘에서의 실행 횟수는 n번 보다 적게 한다는 것을 의미한다.
시간 복잡도를 따지면 n의 함수를 쫙 했을 때 n보다 적게 실행된다.
반복의 경우, for문에서 여러 번 곱했을 것이다.
순환에서는 결과적으로 K+1번 실행된다.
K = log2n 에 해당하는 값이 된다.
(2의 거듭제곱에 관한 예시) 빅오로 보면 로그n에 비례하는 시간이다. 그러므로 훨씬 효율적이다.
반복의 경우, for문에서 여러 번 곱했을 것이다.
문제
1) power(2, 6)과 같이 호출하였을 경우에 호출 체인을 그리시오.
2의 6승을 호출했을 때의 호출 체인을 그리는 것
Power(2, 6)
Power(4, 3)
4 * power(16, 1)
Power(16, 1)
16 * (power(256,0)
Powr(256, 0)
다시 위로 올라가서
최종적으로 64가 리턴된다.
2) 거듭제곱값을 계산하는 함수를 다음의 순환적인 정의를 이용하여 작성하면 실행 시간이 줄어드는가?
시간 복잡도는 n에 비례하는 시간이 된다. 반복적인 방법과 하나도 차이가 없는 무익한 경우에 해당한다.
3. 피보나치 수열의 계산
피보나치 수열은 순환적인 방법으로 계산할 때, 매우 비효율적이다. 같은 항이 중복되어 계산되기 때문이다. 이러한 현상은 n이 커질수록 더욱 심해진다. 반복적인 방법을 사용하면 간단하게 끝나는 것이므로 이 경우에는 순환적인 방법이 비효율적이다.
- 순환적인 피보나치 수열 계산 프로그램
int fib(int n){
if( n==0 ) return 0;
if( n==1 ) return 1;
return (fib(n-1) + fib(n-2));
}
- 반복적인 피보나치 수열 계산 프로그램
int fib_iter(int n){
if ( n==0 ) return 0;
if ( n==1 ) return 1;
int pp = 0;
int p = 1;
int result = 0;
for (int i = 2; i <= n; i++){
result = p + pp;
pp = p;
p = result;
}
return result;
}
2장이 끝났다.