숫자의 거듭제곱, 재귀를 활용하여 계산하기

숫자의 거듭제곱 계산하기

C#에선 제곱을 도와주는 pow라는 함수가 있긴 하지만, 직접 유사한 함수를 효율적으로 재귀를 이용해 작성하여 사용할수도 있습니다. 직접 만들 경우의 단점은 지수가 정수여야한단 점이지만요.

 

거듭제곱의 재귀 탈출 조건

x^n을 계산하려고 가정할때, x의 값이 무엇이든간에 x^0은 1이기 때문에 좋은 탈출 조건입니다.

 

이제 n이 양수일 때 어떻게 계산되야하는지 알아보겠습니다 x의 거듭제곱을 곱할 때는 지수를 더하면 됩니다. 임의의 지수 a, b에 대하여 x^a*x^b = x^a+^b입니다.

 

그러므로 n이 양수이고 짝수일 경우에는 x^n = x^(n/2)*x^(n/2)로 표현가능합니다. 여기서 y = x^(n/2)라고 치면 x^n = y*y으로 계산가능합니다. n이 양수이고 홀수일 경우도 살펴보겠습니다. 이경우 x^n = x^(n-1)*x로 표현가능합니다. 

 

n이 음수일 경우에는 x^n = 1/x^-n이고 지수 -n은 양수가 됩니다. 그러므로 x^-n을 재귀적으로 계산하고 그 역수를 구하면 됩니다.

 

참고: 

지수(거듭제곱)가 0,1,음수일 때 (MyWhyU)

 

x^n을 계산하는 재귀 알고리즘

1. 탈출 조건은 n = 0이고 x^0 = 1일 경우.

2. n이 양수이고 짝수이면 y = x^(n/2)을 재귀적으로 계산한 후 x^n = y*y를 계산합니다. x^(n/2)를 한 번만 계산하고, 이 재귀 호출의 결과를 그 자신과 곱함으로써 단 한 번의 재귀 호출만 해도 된다는 것을 유의해야합니다.

3. n이 양수이고 홀수라면 x^(n-1)을 재귀적으로 계산하여 지수가 0이거나 양수이면서 짝수가 되게 합니다. x^n = x^(n-1)*x가 됩니다.

4. n이 음수이면 x^(-n)을 재귀적으로 계산하여 지수가 양수가 되도록 합니다. 그러면 x^n = 1/x^(-n)이 됩니다.

 

 

코드 작성

static int Power(int x, int n)
{
    //base case
    if(n==0)
    {
        return 1;
    }

    if(/*홀수라면*/)
    {

    }

    if(/*짝수라면*/)
    {

    }

    if(/*음수라면*/)
    {

    }

}

위 의사코드를 작성하면 이러한 틀이 나옵니다. 홀수일때와 짝수일때를 판정하는 함수를 만들어줘서 관리하겠습니다. 음수일때는 n<0보다 작은 경우이니 그냥 적으면 됩니다.

 

class Program {
    static void Main(string[] args)
    {
        Console.WriteLine(Power(3, -1));
        Console.WriteLine(Power(3, 0));
        Console.WriteLine(Power(3, 1));
        Console.WriteLine(Power(3, 2));
    }

    static float Power(int x, int n)
    {
        //base case
        if(n==0)
        {
            return 1;
        }

        if (n < 0)
        {
            return 1 / Power(x, -n);
        }

        if (IsOdd(n))
        {
            return x*Power(x, n - 1);
        }

        if (IsEven(n))
        {
            var y = Power(x, n / 2);
            return y * y;
        }

        return 0;
    }

    private static bool IsEven(int n)
    { 
        return n%2==0;
    }

    private static bool IsOdd(int n)
    {

        return !IsEven(n);
    }
}

정상적으로 출력됨을 확인했습니다.

 

재귀에서 중요한건 미리 문제를 분석하고 하위문제가 무엇인지 알아내는게 중요한 것 같습니다. 막상 재귀 문제를 풀게되면 어렵겠습니다... -_-;;