어떤 수의 거듭제곱은 x^y 형태로 나타낼 수 있습니다. 여기서 x는 밑(base), 즉 거듭제곱의 대상이 되는 수이고, y는 지수(power)입니다.
예를 들면 다음과 같습니다.
x = 2, y = 10이라고 가정 x^y = 1024 여기서 x^y는 곧 2^10을 의미합니다.
재귀(recursion)를 이용해 거듭제곱을 구하는 프로그램은 아래와 같습니다.
예제 코드
#include <iostream>
using namespace std;
int FindPower(int base, int power) {
if (power == 0)
return 1;
else
return (base * FindPower(base, power-1));
}
int main() {
int base = 3, power = 5;
cout<<base<<"의 "<<power<<"제곱은 "<<FindPower(base, power);
return 0;
}
실행 결과
3의 5제곱은 243
코드 설명
위 프로그램에서 FindPower() 함수가 바로 재귀 함수입니다. 이 함수의 동작 방식은 다음 두 가지로 나눌 수 있습니다.
1. 기저 사례(Base Case): 지수가 0이면 함수는 1을 반환합니다. 어떤 수를 0제곱하면 항상 1이 되기 때문입니다.
2. 재귀 호출: 지수가 0이 아니라면, 함수는 지수를 1씩 줄여가며 자기 자신을 재귀적으로 호출하고, 그 결과에 밑을 곱해 반환합니다.
int FindPower(int base, int power) {
if (power == 0)
return 1;
else
return (base * FindPower(base, power-1));
}
예를 들어 3의 5제곱은 다음과 같은 단계를 거쳐 계산됩니다.
3^5 = 3 × 3^4 = 3 × 3 × 3^3 = 3 × 3 × 3 × 3^2 = 3 × 3 × 3 × 3 × 3^1 = 3 × 3 × 3 × 3 × 3 × 3^0 = 3 × 3 × 3 × 3 × 3 × 1 = 243
main() 함수에서는 FindPower() 함수를 최초로 호출하여 거듭제곱을 계산한 뒤, 그 결과를 화면에 출력합니다.
이 프로그램의 시간 복잡도는 지수의 크기에 비례하는 O(n)입니다. 참고로 분할 정복 기법을 활용하면 O(log n)의 시간 복잡도로 더 빠르게 계산할 수도 있습니다.