[Algorithm/문해기] 재귀(recursion)_거듭제곱

거듭제곱 값을 구하기 위해서는 '재귀함수'를 이용할 수 있다.

그러나 재귀함수에 대한 점화식을 어떻게 작성하는지에 따라 시간복잡도가 크게 달라질 수 있다. 

 

방법 1.  

가장 기본적인 아이디어로 n=0 이될 때까지 x값을 반환하는 형태이다. 

float power(float x, int n) { if (n == 0) return 1.0; else return x * power(x,n-1); }

이 방식대로 거듭제곱의 결과를 구한다면, 시간복잡도는 'n' 이된다. 

 

방법 2.

n/2일때의 메모리를 불러와 이용하는 방식.

만약 2**5 을 구하고자 한다면

2**5 = (2**2)*( 2**2 )*2 이고

2**2 = (2**1)*(2**1)이 되므로 5번의 연산을 시행해 주어야 하는 방법1과 달리 2번의 연산과정으로 답을 구할 수 있다.

float power(float x, int n) { float y; if (n == 0) return 1.0; else if (n == 1) return x; else { y = power(x,n/2); if (even(n)) return y * y; else return x * y * y;

방법2의 시간복잡도는 'logN'이 된다.