1. recursive algorithm ( 재귀 알고리즘 )
2. iterative algorithm ( 반복 알고리즘 )
Recursive 란 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법이다.
대개 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법이다.
가장 기본적인 재귀 알고리즘을 생각하여 보자.
1. 팩토리얼
n! 의 계산식은 n = 1 일 때는 1
n >=2 일 때는 n*(n-1)! 이다.
이것을 단순한 반복접근 방식으로 해결해보자.
1) iterative approach
n! = 1x2x3x....xn
int fact ( int n ) {
int res = 1;
int i;
for (i = 1; i <= n , i++)
res = res * i ;
return res;
}
단순히 for문을 사용하여 n번 반복하고 있다.
2) recursive approach
int fact(int n){
if( n <=1 ) return 1;
else return n*fact(n-1);
}
재귀 접근방식으로는 코드가 아주 간단해졌다. 팩토리얼의 수학적 정의를 그대로 이용한 것이다.
만약 n=5라면 몇 번이 실행될까.
iterative 방식이라면 당연히 5번 반복될 것이다.
recursive 방식이라면
fact (5) = 5* fact(4)
= 5*4*fact(3)
= 5*4*3*fact(2)
= 5*4*3*2*fact(1)
= 5*4*3*2*1
=120
4번? 5번? 정답은 5번이다.
fact(4) -> fact (3) -> fact (2) -> fact(1) -> 1
fact(4)는 fact(5)가 실행한것이며 fact(3)은 fact(4) 라는 함수 안에서 실행한 것이다.
1은 fact(1)이라는 함수안에서 실행한 결과이다.
결국 iterative 방식과 recursive 방식 모두 n이라는 결과가 나왔다.
항상 이렇게 두 방식의 성능이 똑같은 것은 아니다.
그렇다면 recursive 방식의 성능이 월등히 우월한 경우를 살펴보자.
그 전에 recursive 방식의 특징을 반드시 알아야 한다.
Recursive function은 반드시 2부분을 포함해야 한다.
a) recursive call을 하는 부분
b) recursive call을 멈추는 부분
앞서 살펴본 팩토리얼의 경우도 if문을 통하여 n<=1 라는 조건을 통하여 return 1;로 멈추는 부분이 있었다. 이 부분이 없다면 시스템 오류가 발생할 때까지 무한정 호출되게 된다.
2. 거듭제곱
1) iterative approach
double iter_power(double x, int n ){
int i;
double r= 1.0;
for(i=0; i<n ;i++)
r=r*i;
return r;
}
단순히 for을 사용하여 x의 n승을 계산하고 있다.
2) recursive approach
double 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);
}
위의 알고리즘은 상당히 좋은 아이디어를 사용하여 만들어진 알고리즘이다.
if문을 사용하여 recursive를 멈추는 부분과 조건에 따라 2개의 recursive 호출을 하는 부분으로 나누어 진다.
위의 코드를 수학식으로 나타낸다면
n= 짝수일 때
power ( x , n ) = power ( x*x, n/2 )
n= 홀수일 때
power ( x , n ) =x* power ( x*x, n-1/2 )
즉 2의 10승을 계산할 때 2를 10번 곱하는 것보다는 4를 5번 곱하는 것이 더 효율적이라는 것이다.
2의 10승을 계산할 때는 -> 4의 5승 으로
4의 5승을 계산할 때는 -> 4* 16의 2승으로
16의 2승을 계산할 때는 -> 256의 1승으로 계산하여 현저하게 곱하는 횟수를 감소시킨다.
총 수행 횟수는
n = 10일 때
power(2,10) = power(4,5) -> power(16,2) -> power(256 ,1) -> power(256*256,0) -> 1
5번을 호출하게 됩니다.
iterative 방식이 10번을 다 호출하게 되는 것과는 달리 recursive 방식은 그의 절반인 5번만을 호출하게 됩니다.
정확히 수학식으로 표현하면 [ logn ]+2 로 표현됩니다. ([] 가우스내림 ) (n=1부터 해보세요 ㅋ )
빅오 표기법으로 나타내보면 두 방식의 성능은 O(n)과 O(logn) 으로 n이 커질 때 엄청난 성능 차이를 보이게 됩니다.
이 때문에 많은 알고리즘에서 거듭제곱을 사용할 때 recursive 알고리즘을 사용합니다.
Posted by 사라링
