[자료구조] Recursion
1. Recursion
Recursion 이란?
=> algorithm이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
=> 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법
Recursion을 사용한 algorithm
=> factorial 값 구하기
=> Fibonacci 수열
=> 이항계수
=> Hanoi 탑
=> 이진탐색
factorial 값 구하기
=> factorial 이란? n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다.
factorial 구현 방법
=> 1번째 방법
=> factorial1 함수와 그 외의 sub 함수를 따로 제작
int factorial1(int n) {
if( n<= 1 ) return(1);
else return (n * factorial2(n-1));
}
int factorial2(int n) {
if( n<= 1 ) return(1);
else return (n * factorial3(n-1));
}
int factorial3(int n) {
if( n<= 1 ) return(1);
else return (n * factorial4(n-1));
}
//...=> 2번째 방법
=> Recursion을 이용하여 자기 자신을 다시 호출
int factorial(int n) {
if( n<= 1 ) return(1);
else return (n * factorial(n-1));
}
factorial 함수의 순환 호출 순서
순환 Algorithm의 구조
=> 순환 algorithm은 순환 호출을 하는 부분 / 순환 호출을 멈추는 부분이 필요하다.
=> 순환 호출을 멈추는 부분이 없다면 오류가 발생할 때까지 무한정 호출하게 된다. (무한루프)
2. 순환과 반복
Computer에서의 되풀이
=> 순환(recursion) : 순환 호출 이용
=> 반복(iteration) : for또는 while을 이용한 반복
순환
=> 순환적인 문제에서는 자연스러운 방법
=> 함수 호출의 overhead
반복
=> 수행속도가 빠르다.
=> 순환적인 문제에 대해서는 program 작성이 아주 어려울 수도 있다.
대부분의 순환은 반복으로 바꾸어 작성할 수 있다.
// Factorial의 반복적 구현
int factorial_iter(int n) {
int k, v = 1;
for(k = 1; k <= n; k++)
v = v * k;
return v;
}
ex) 거듭제곱 문제
=> 순환적인 방법이 반복적인 방법보다 더 효율적인 예
=> 숫자 x의 n제곱 값을 구하는 문제 : Xⁿ
// 반복적인 방법
double sqr_iter(double x, int n) {
int i;
double r = 1.0;
for(i = 0; i < n; i++)
r = r * x;
return r;
}// 순환적인 방법
double sqr_recur(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);
}
성능 분석
=> 순환적인 방법의 시간 복잡도
=> 만약 2의 10제곱이라면 2^10 -> 2^9 -> 2^8 ... 2² -> 2¹ -> 2º
=> 시간복잡도 : O(log₂ n)
=> 반복적인 방법과 순환적인 방법의 비교
| 반복적인 방법 | 순환적인 방법 | |
| 시간 복잡도 | O(n) | O(log₂ n) |
ex) Fibonacci 수열
=> 순환 호출을 사용하면 비효율적인 예
=> 순환 호출을 사용할 경우 이전에 계산한 값을 다시 계산하게 됨
// 반복적인 방법
int fib_iter(int n) {
if(n < 2) return n;
else {
int i, cur, fi1 = 1, fi2 = 0;
for(i = 2; i <= n; i++) {
cur = fi1 + fi2;
fi2 = fi1;
fi1 = cur;
}
return cur;
}
}// 순환적인 방법
int fib_recur(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
return (fib_recur(n-1) + fib_recur(n-2));
}
https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9