Problem
Compute base to the power exponent with recursion: x⁰ = 1, and xⁿ = (x^(n/2))² for even n or x × (x^((n−1)/2))² for odd n. This uses far fewer multiplications than a simple loop.
Implement recursive_power(base, exponent).
Input
base: The base. exponent: The exponent (zero or positive).
Output
Return base raised to exponent.
Constraints
-10 ≤ base ≤ 10; 0 ≤ exponent ≤ 18
Examples
Input:
base = 3
exponent = 5
Expected output:
expected = 243Input:
long long base = 3;
long long exponent = 5;
Expected output:
long long expected = 243;Input:
long base = 3;
long exponent = 5;
Expected output:
long expected = 243;Explanation
3⁵ = 3 × (3²)² = 3 × 81 = 243.
Input:
base = 7
exponent = 0
Expected output:
expected = 1Input:
long long base = 7;
long long exponent = 0;
Expected output:
long long expected = 1;Input:
long base = 7;
long exponent = 0;
Expected output:
long expected = 1;Explanation
The base case: anything to the power 0 is 1.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Use the exponent’s parity to shrink the problem size quickly.
Hint 2
Recursive squaring avoids repeating work and cuts the number of multiplications drastically.
Hint 3
Be careful with the zero exponent and the base case for tiny exponents.
Expected complexity
O(log exponent) time, O(log exponent) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.