[C][순환][반복] 거듭제곱의 값 계산

프로그래밍 언어에서 되풀이하는 방법으로는 반복(iteration)과 순환(recursion)이 있다.

반복은 for나 while 등의 반복 구조를 사용해 반복하는 것을 말하며, 대부분의 경우 순환에 비해 간명하고 효율적이다.

그러나 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 순환은 반복에 비해 알고리즘을 훨씬 명확하거나 간결하게 나타나낼 수 있는 장점을 가지기도 한다.

순환 중에서 끝에서 이루어지는 순환을 꼬리 순환(tail recursion)이라 하고, 앞에서 이루어지는 순환을 머리 순환(head recursion)이라 한다. 

꼬리 순환은 반복 알고리즘으로 쉽게 바꾸어 쓸 수 있으나, 머리 순환이나 함수 내부 여러 군데에서 자기 자신을 호출하는 경우(multi recursion) 쉽게 반복 알고리즘으로 바꿀 수 없다.

일반적으로 동일한 알고리즘을 꼬리 순환과 머리 순환 중 어떤 것으로든 바꿀 수 있다면, 꼬리 순환을 선택하여야 한다.

이번에는 거듭제곱 값 계산을 통해 순환 알고리즘이 반복 알고리즘보다 빠른 경우를 살펴 보겠다.

간단하게 생각 할 수 있는 반복 알고리즘을 사용해 코드를 작성해보았다.

#include <stdio.h>
 
double power_iteration(double x, int n) { // x는 밑, n은 지수이다.
    int i;
    double r = 1.0;
    for (i = 0; i < n; i++)
       r = r * x;
    return (r);
}
 
int main(void) {
    double base = 2.0;
    int exponent = 10;
    double result;
    
    result = power_iteration(base, exponent);
    printf("계산 결과: %.2f\n", result);
    
    return 0;
}

다음으로는 순환 알고리즘을 통해 코드를 작성하겠다.

순환에서 중요한 것은 순환을 할 때마다 문제의 크기가 작아진다는 것이다.

거듭제곱에서는 어떻게 크기를 줄일 수 있을까?

먼저 x^n 이라는 거듭제곱이 있을 때 n이 짝수라고 생각해보자.

이 때 지수를 줄일 수 있는 방법은 x^n 을 (x^2)^(n/2)로 표현하는 것이다.

n이 홀수일 때는 n이 짝수가 될 수 있도록 해주면 된다.

x^n 은 곧 x * x^(n-1)이고 n이 홀수이므로 n-1은 짝수이다.

x^(n-1)은 거듭제곱 꼴이고 지수가 짝수이므로, 위에서 사용한 방법을 사용하면 (x^2)^((n-1)/2))라고 할 수 있다.

즉 n이 홀수인 경우 x^n은 x * (x^2)^((n-1)/2))이다.

이러한 개념을 이용해 코드를 작성하면 다음과 같다.

#include <stdio.h>
 
double power_recursion(double x, int n) { // x는 밑, n은 지수이다.
    if (n == 0) return 1;
    else if ((n % 2) == 0) // n이 짝수인 경우
        return power_recursion(x*x, n/2);
    else return x * power_recursion(x*x, (n-1)/2); // n이 홀수인 경우
}
 
int main(void) {
    double base = 2.0;
    int exponent = 10;
    double result;
    
    result = power_recursion(base, exponent);
    printf("계산 결과: %.2f\n", result);
    
    return 0;
}

글을 시작할 때 대부분의 경우에는 반복이 순환보다 효율적이다고 하였다.

하지만 이 경우는 순환이 더 효율적이다.

어째서일까?

이는 아까 언급한 바와 같이 순환 호출이 이루어 질 때마다 문제의 크기가 작아지기 때문이다.

예를 들어 n을 100이라고 가정하자.

이 때 n의 크기는 호출 할 때 마다 100 -> 50 -> 25 -> 12 -> 6 -> 3 -> 1 로 작아진다.

즉 순환 알고리즘의 시간 복잡도는 O(logn)이다.

반면 반복 알고리즘일 때는 n이 100이라면 100번의 연산이 이루어진다.

따라서 반복 알고리즘의 시간 복잡도는 O(n)이다.

이번 예제를 통해 일반적인 경우와 달리 순환 알고리즘이 반복 알고리즘보다 효율적인 경우를 살펴보았다.

• 파보나치 수열의 계산을 통해 순환 알고리즘과 반복 알고리즘 비교해보기
• 순환 알고리즘을 통해 하노이탑 문제 해결해보기
• 이항 계수의 계산을 통해 순환 알고리즘과 반복 알고리즘 비교해보기