재귀적 거듭제곱

문제

base의 exponent 거듭제곱을 재귀적으로 계산하세요: x⁰ = 1, 그리고 xⁿ = (x^(n/2))² (n이 짝수일 때), 또는 x × (x^((n−1)/2))² (n이 홀수일 때)입니다. 이 방식은 단순 반복문보다 곱셈 횟수가 훨씬 적습니다.

recursive_power(base, exponent)를 구현하세요.

base: 밑수입니다. exponent: 지수입니다 (0 또는 양의 정수).

base를 exponent만큼 거듭제곱한 값을 반환하세요.

-10 ≤ base ≤ 10; 0 ≤ exponent ≤ 18

예시 1

입력:
base = 3
exponent = 5

예상 출력:
expected = 243

입력:
long long base = 3;
long long exponent = 5;

예상 출력:
long long expected = 243;

입력:
long base = 3;
long exponent = 5;

예상 출력:
long expected = 243;

3⁵ = 3 × (3²)² = 3 × 81 = 243.

예시 2

입력:
base = 7
exponent = 0

예상 출력:
expected = 1

입력:
long long base = 7;
long long exponent = 0;

예상 출력:
long long expected = 1;

입력:
long base = 7;
long exponent = 0;

예상 출력:
long expected = 1;

기저 사례: 어떤 수든 0 제곱은 1입니다.

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

지수의 홀짝성을 이용해 문제 크기를 빠르게 줄이세요.

힌트 2

재귀적 제곱은 중복 계산을 줄여 곱셈 횟수를 크게 줄입니다.

힌트 3

지수가 0인 경우와 작은 지수의 base case를 주의하세요.

예상 복잡도

시간 O(log exponent), 추가 공간 O(log exponent)

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.