Power of a Number Using Recursion
Description
Given an integer x and a non-negative integer n, return x to the power n, x multiplied by itself n times, using recursion. x to the power 0 is 1, for every x including 0.
Examples
Example 1
Input: x = 2, n = 5
Output: 32
Explanation: 2 × 2 × 2 × 2 × 2 = 32.
Example 2
Input: x = 3, n = 0
Output: 1
Explanation: Anything to the power 0 is 1.
Example 3
Input: x = -2, n = 3
Output: -8
Explanation: (-2) × (-2) × (-2) = -8: an odd power of a negative number is negative.
Example 4
Input: x = 0, n = 0
Output: 1
Explanation: 0 to the power 0 is taken to be 1, like every power 0.
Constraints
- -9 ≤ x ≤ 9
- 0 ≤ n ≤ 16
Editorial
Brute Force - One Factor per Call
Intuition
x^n is x times x^(n - 1): one factor of x, then the same problem one smaller. The smallest exponent is 0, and x^0 is 1, the empty product, so that's the base case. Each call hands n - 1 on and multiplies what comes back by x.
Step-by-Step Explanation
Let's trace Example 1, x = 2, n = 5:
power(2, 5) = 2 × power(2, 4) = 2 × 16 = 32.power(2, 4) = 2 × power(2, 3) = 2 × 8 = 16.power(2, 3) = 2 × power(2, 2) = 2 × 4 = 8.power(2, 2) = 2 × power(2, 1) = 2 × 2 = 4.power(2, 1) = 2 × power(2, 0) = 2 × 1 = 2.power(2, 0)is the base case: it returns 1.
One Factor per Call — Each call waits for the one below it; the answers come back up, one factor of 2 at a time.
Algorithm
- If
nis 0, return 1. - Otherwise return
x * power(x, n - 1).
Code
class Solution {
public:
long long power(int x, int n) {
if (n == 0) return 1; // anything to the power 0 is 1
return x * power(x, n - 1);
}
};
class Solution:
def power(self, x: int, n: int) -> int:
if n == 0:
return 1 # anything to the power 0 is 1
return x * self.power(x, n - 1)
class Solution {
public long power(int x, int n) {
if (n == 0) return 1; // anything to the power 0 is 1
return x * power(x, n - 1);
}
}
var power = function(x, n) {
if (n === 0) return 1; // anything to the power 0 is 1
return x * power(x, n - 1);
};
Complexity Analysis
Time Complexity: O(n)
One call per exponent, n + 1 in all: 17 for n = 16.
Space Complexity: O(n)
The calls wait on the stack, n + 1 frames at the deepest.
Why This Approach Is Not Efficient
Here n is at most 16, so it makes at most 17 calls, nothing at all. But the count grows with n, one call per factor. Halving the exponent shrinks the problem much faster: x^10 is (x^5)², so one call for x^5 replaces five. For n = 16 that's 6 calls instead of 17, and for n = 1,000,000, 21 instead of a million and one.
Optimal Approach - Halve the Exponent
Intuition
When n is even, x^n = (x^(n/2))²; when it's odd, n // 2 drops one, so x^n = (x^(n//2))² × x. Either way, work out x^(n//2) once, keep it in a variable, and square it. Calling power twice for the two halves would undo the saving.
Step-by-Step Explanation
Let's trace the same example, x = 2, n = 5:
power(2, 5) = 4 × 4 × 2 = 32: 5 is odd, so one more 2.power(2, 2) = 2 × 2 = 4.power(2, 1) = 1 × 1 × 2 = 2: 1 is odd, so one more 2.power(2, 0)returns 1.
Halve the Exponent — The exponent halves at each call: 5, 2, 1, 0. Each answer is squared on the way back, with one more 2 for an odd exponent.
Algorithm
- If
nis 0, return 1. half = power(x, n // 2).- Return
half * half, times one morexwhennis odd.
Code
class Solution {
public:
long long power(int x, int n) {
if (n == 0) return 1;
long long half = power(x, n / 2); // x^(n / 2), worked out once
return half * half * (n % 2 == 1 ? x : 1); // one more x when n is odd
}
};
class Solution:
def power(self, x: int, n: int) -> int:
if n == 0:
return 1
half = self.power(x, n // 2) # x^(n // 2), worked out once
return half * half * (x if n % 2 else 1) # one more x when n is odd
class Solution {
public long power(int x, int n) {
if (n == 0) return 1;
long half = power(x, n / 2); // x^(n / 2), worked out once
return half * half * (n % 2 == 1 ? x : 1); // one more x when n is odd
}
}
var power = function(x, n) {
if (n === 0) return 1;
const half = power(x, Math.floor(n / 2)); // x^(n / 2), worked out once
return half * half * (n % 2 === 1 ? x : 1); // one more x when n is odd
};
Complexity Analysis
Time Complexity: O(log n)
The exponent halves at every call, so about log₂ n + 2 calls.
Space Complexity: O(log n)
One frame per call on the stack.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Stopping at n = 1. if n == 1:
On x = 3, n = 0 it fails with RecursionError: maximum recursion depth exceeded in comparison instead of returning 1. With n == 1 as the only base case, a call with n = 0 goes on to n = -1, -2, and never stops, until Python gives up with a RecursionError. The smallest exponent is 0, so that's the base case: x^0 = 1.
Returning 0 for n = 0. return 0
On x = 2, n = 5 it returns 0; the answer is 32. x^0 is 1, the empty product. Returning 0 there makes every answer 0, since each call multiplies by what the base case returned.
Forgetting odd exponents. return half * half
On x = 2, n = 5 it returns 1; the answer is 32. x^n = (x^(n/2))² only when n is even. For odd n, n // 2 drops one, so one more factor of x is needed: x^5 = (x²)² × x.
Where This Pattern Is Taught
This problem practises a base case and a smaller call, and splitting a problem in half. It's taught in Introduction to Recursion and Thinking Recursively.