問題
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.
制約
-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;解説
The base case: anything to the power 0 is 1.
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
指数の偶奇を使うと、問題をすばやく小さくできます。
ヒント 2
再帰的な二乗計算なら重複計算を避けられ、乗算回数を大きく減らせます。
ヒント 3
0乗と、小さい指数のベースケースに注意してください。
目安の計算量
時間 O(log exponent)、追加メモリ O(log exponent)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。