How do you compute x to the power n efficiently with recursion?
Use divide and conquer: x^n equals (x^(n/2)) squared, times x if n is odd. That halves n each time, so it needs only O(log n) multiplications instead of O(n).
Explain it simply
Computing 2^10 by multiplying 2 ten times takes ten steps. But 2^10 is just 2^5 times 2^5, and 2^5 is 2^2 times 2^2 times 2. Each step halves the exponent, so you need only about log2(n) steps, like folding a paper in half again and again.
Compute the half power once, store it, and square it. Calling the function twice would throw away the saving.
Example
function power(x, n) {
if (n === 0) return 1;
if (n < 0) return 1 / power(x, -n);
const half = power(x, Math.floor(n / 2));
return n % 2 === 0 ? half * half : half * half * x;
}
console.log(power(2, 10)); // Output: 1024
console.log(power(3, 5)); // Output: 243
console.log(power(2, -2)); // Output: 0.25Complexity
Time O(log n), space O(log n) for the call stack.
What to say in the interview
"If n is zero the answer is 1. Otherwise I compute x to the power n/2 once, square it, and multiply by x when n is odd. The exponent halves each call, giving O(log n) time and O(log n) stack space. Negative exponents use the reciprocal."
Common mistakes
- Calling power(x, n/2) twice, which turns O(log n) back into O(n).
- Forgetting the odd case.