재귀 알고리즘 #1 팩토리얼과 거듭제곱

문제를 해결하는데 있어서 우리는 두 가지 방식을 사용할 수 있다.

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 알고리즘을 사용합니다.