C#에서 역추적(재귀) 기법으로 주어진 숫자의 거듭제곱을 구하는 방법

C#에서 재귀 호출을 활용하면 주어진 숫자의 거듭제곱을 효율적으로 계산할 수 있습니다. 이 글에서는 밑이 되는 숫자 x와 지수 n을 받아 거듭제곱 값을 반환하는 FindPower 함수를 만드는 방법을 단계별로 살펴봅니다.

거듭제곱 계산 알고리즘의 원리

이 알고리즘의 핵심 아이디어는 다음과 같습니다.

• 숫자 x와 지수 n을 매개변수로 받으며, x는 밑(base), n은 곱셈을 반복할 횟수를 의미합니다.
• n이 0이 되면 1을 반환하며 재귀 호출을 종료합니다.
• n이 짝수라면 절반 지수의 결과를 제곱하여(x * x 형태) 반환합니다.
• n이 홀수라면 결과에 x를 한 번 더 곱하여 반환합니다.

예를 들어 숫자 2와 8이 주어졌다면, 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256이 됩니다.

이 방식은 지수를 절반씩 줄여가며 계산하는 분할 정복(divide and conquer) 기법으로, 일반적인 반복문 방식(O(n))보다 빠른 O(log n)의 시간 복잡도를 가집니다.

예제 코드

using System;
namespace ConsoleApplication{
    public class BackTracking{
        public int FindPower(int x, int n){
            int result;
            if (n == 0){
                return 1;
            }
            result = FindPower(x, n / 2);
            if (n % 2 == 0){
                return result * result;
            }
            else{
                return x * result * result;
            }
        }
    }
    class Program{
        static void Main(string[] args){
            BackTracking b = new BackTracking();
            int res = b.FindPower(2, 8);
            Console.WriteLine(res);
        }
    }
}

코드 설명

1. 종료 조건: n이 0이면 1을 반환하여 재귀를 멈춥니다.
2. 절반 계산: FindPower(x, n / 2)를 호출해 지수를 절반으로 나눈 거듭제곱을 먼저 구합니다.
3. 결합: n이 짝수면 result * result를, 홀수면 x * result * result를 반환합니다.

실행 결과

256

위 코드를 실행하면 2의 8제곱인 256이 출력됩니다. 이처럼 재귀와 분할 정복을 활용하면 적은 연산 횟수로 거듭제곱을 빠르게 계산할 수 있습니다.