Better recursive raise to power

You are sitting across from a Microsoft interviewer who writes 2^10 = 1024 on the whiteboard, then asks: "How would you compute this without using any built-in power function, and faster than multiplying 2 by itself ten times?" This problem, also known as Pow(x, n) on other platforms, tests your ability to optimize a brute-force recursive solution using a classic divide-and-conquer trick. It is a staple of technical interviews because it bridges simple recursion with logarithmic thinking.

TL;DR

Raise a number to a power recursively by exploiting even exponents: square the base and halve the exponent, cutting the problem in half each time. Handle negative exponents by inverting the base. The base case returns 1 when the exponent reaches 0. This runs in O(log n) time and space, compared to the naive O(n) approach.

Why This Problem Matters

Exponentiation by squaring is one of those small problems that packs a disproportionate teaching punch. It requires you to think about how mathematical properties can shortcut computation, and the same halving strategy shows up in binary search, merge sort, and modular arithmetic in cryptography. Microsoft and other companies use it to gauge whether a candidate can move beyond brute force.

The Naive Approach and Its Problem

The simplest way to compute base^exponent is to multiply the base by itself exponent times:

// Naive: O(n) time, O(n) space
public double naivePow(double base, int exponent) {
    if (exponent == 0) return 1.0;
    return base * naivePow(base, exponent - 1);
}

This works, but every call just decrements the exponent by 1. For pow(2, 8), that means 8 recursive calls stacked on top of each other:

Eight calls for an exponent of 8. For an exponent of 1,000,000, that is a million stack frames. We can do much better.

The Key Insight: Squaring Halves the Work

Here is the mathematical property that changes everything:

• If n is even: x^n = (x^2)^(n/2) ... square the base, halve the exponent
• If n is odd: x^n = x * x^(n-1) ... peel off one factor, making the exponent even

Instead of reducing the exponent by 1 each step, we cut it in half whenever it is even. That turns an O(n) chain into an O(log n) tree.

For pow(2, 8):

• pow(2, 8) - exponent is even, so compute pow(2*2, 8/2) = pow(4, 4)
• pow(4, 4) - even again, pow(16, 2)
• pow(16, 2) - even again, pow(256, 1)
• pow(256, 1) - odd, so 256 * pow(256, 0) = 256 * 1 = 256

Four calls instead of eight:

Handling Negative Exponents

Negative exponents follow a simple rule from algebra: x^(-n) = (1/x)^n. So before entering the main recursion, convert to a positive exponent by inverting the base:

pow(2, -3) becomes pow(0.5, 3), which equals 0.125.

The negative-exponent case only fires once, at the top of the recursion, adding zero extra overhead.

Handling Mixed Odd and Even Exponents

When odd and even exponents alternate, the algorithm seamlessly switches strategies. Here is pow(2, 9):

The odd step at the top peels off a single factor of 2. After that, the exponent is 8 (even), and the squaring-and-halving kicks in. The total depth is still O(log n).

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {

  public double betterPow(double base, int exponent) {
    // Base case: anything raised to the 0th power is 1
    if (exponent == 0) return 1.0;

    // Negative exponent: invert the base, negate the exponent
    if (exponent < 0) return betterPow(1 / base, -exponent);

    // Odd exponent: peel off one factor to make the exponent even
    if (exponent % 2 == 1) return base * betterPow(base, exponent - 1);

    // Even exponent: square the base, halve the exponent
    return betterPow(base * base, exponent / 2);
  }
}

Let's trace through betterPow(2, 3) step by step:

1. betterPow(2, 3) - exponent is odd, return 2 * betterPow(2, 2)
2. betterPow(2, 2) - exponent is even, return betterPow(4, 1)
3. betterPow(4, 1) - exponent is odd, return 4 * betterPow(4, 0)
4. betterPow(4, 0) - base case, return 1.0

Unwinding: 4 * 1.0 = 4, then betterPow(2, 2) = 4, then 2 * 4 = 8. Correct.

And betterPow(3, -1):

1. betterPow(3, -1) - negative exponent, return betterPow(1/3, 1)
2. betterPow(0.333..., 1) - odd, return 0.333... * betterPow(0.333..., 0)
3. betterPow(0.333..., 0) - base case, return 1.0

Result: 0.333.... Correct.

Complexity Analysis

Time Complexity: O(log n)

Each even step halves the exponent. When the exponent is odd, decrementing by 1 makes it even, so the very next step halves it. The exponent reaches 0 in at most 2 * log2(n) steps, which simplifies to O(log n).

For betterPow(2, 8): only 4 calls. For betterPow(10, 1000000): roughly 20 calls. That is a massive improvement over the naive million-call version.

Space Complexity: O(log n)

Each recursive call adds a frame to the call stack. Since the maximum recursion depth is O(log n), the space usage is also O(log n). An iterative version of the same algorithm can achieve O(1) space, which is worth mentioning in an interview if the interviewer asks about optimization.

Common Pitfalls

1. Forgetting the base case. Without if (exponent == 0) return 1.0, the recursion never terminates. This is the anchor that stops the halving.

2. Not handling negative exponents. If you only handle positive exponents, betterPow(2, -3) recurses forever (decrementing past 0 into more negative values). Always convert negatives upfront.

3. Integer division with odd exponents. In Java, 3 / 2 gives 1, not 1.5. That is actually what we want here, but forgetting the odd-exponent branch and always halving would skip the remainder. The exponent % 2 == 1 check prevents this.

4. Returning int instead of double. Since negative exponents produce fractional results, the return type must be double (or float). Returning an integer truncates 0.333... to 0.

Interview Tips

When this problem comes up in an interview:

1. Start with the naive version. Write out the simple O(n) recursion first. This shows you understand the problem before optimizing.

2. Explain the math. Say "x to the n equals x-squared to the n-over-two when n is even" and write the formula on the whiteboard. Interviewers want to see you derive the optimization, not memorize it.

3. Walk through an example. Trace betterPow(2, 10) on paper, showing how the exponent shrinks: 10, 5, 4, 2, 1, 0. Six calls instead of ten.

4. Mention the iterative alternative. If asked about space optimization, explain that you can convert the recursion to a loop with O(1) space by maintaining a running result and squaring the base in each iteration.

5. Handle edge cases verbally. Mention base = 0 with a negative exponent (division by zero), exponent = 0 returning 1 for any base, and very large exponents fitting within the constraints.

Key Takeaways

• Exponentiation by squaring transforms O(n) recursion into O(log n) by halving the exponent whenever it is even, squaring the base to compensate.
• Negative exponents are handled with a one-time conversion: invert the base and negate the exponent, then proceed normally.
• The three-branch structure (base case, odd exponent, even exponent) covers all cases cleanly and is the standard interview answer for this problem.
• This same halving pattern appears in binary search, merge sort, and modular exponentiation in cryptography, so mastering it here pays dividends across many problems.

Practice and Related Problems

Once you are comfortable with this problem, try these to reinforce the recursive thinking:

• Nth Fibonacci number with recursion (similar memoization and optimization patterns)
• Is Power of Two (tests the same even/odd reasoning on powers)
• Reverse an integer (another number-manipulation recursion problem)

This problem and hundreds more are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Consistent practice with problems like this builds the pattern recognition that separates strong interview performances from average ones.

Solutions in Other Languages

Python

class Solution:
    def better_pow(self, base: float, exponent: int) -> float:
        if exponent == 0:
            return 1.0

        if exponent < 0:
            return self.better_pow(1 / base, -exponent)

        if exponent % 2 == 1:
            return base * self.better_pow(base, exponent - 1)

        return self.better_pow(base * base, exponent // 2)

JavaScript

class Solution {
  betterPow(base, exponent) {
    if (exponent === 0) return 1.0;

    if (exponent < 0) return this.betterPow(1 / base, -exponent);

    if (exponent % 2 === 1) return base * this.betterPow(base, exponent - 1);

    return this.betterPow(base * base, Math.floor(exponent / 2));
  }
}

TypeScript

class Solution {
  betterPow(base: number, exponent: number): number {
    if (exponent === 0) return 1.0;

    if (exponent < 0) return this.betterPow(1 / base, -exponent);

    if (exponent % 2 === 1) return base * this.betterPow(base, exponent - 1);

    return this.betterPow(base * base, Math.floor(exponent / 2));
  }
}

C++

class Solution {
public:
  double betterPow(double base, int exponent) {
    if (exponent == 0)
      return 1.0;

    if (exponent < 0)
      return betterPow(1 / base, -exponent);

    if (exponent % 2 == 1)
      return base * betterPow(base, exponent - 1);

    return betterPow(base * base, exponent / 2);
  }
};

Go

func (s *Solution) BetterPow(base float64, exponent int) float64 {
    if exponent == 0 {
        return 1.0
    }

    if exponent < 0 {
        return s.BetterPow(1/base, -exponent)
    }

    if exponent%2 == 1 {
        return base * s.BetterPow(base, exponent-1)
    }

    return s.BetterPow(base*base, exponent/2)
}

Scala

class Solution {
  def betterPow(base: Double, exponent: Int): Double = {
    if (exponent == 0) 1.0
    else if (exponent < 0) betterPow(1 / base, -exponent)
    else if (exponent % 2 == 1) base * betterPow(base, exponent - 1)
    else betterPow(base * base, exponent / 2)
  }
}

Kotlin

class Solution {
  fun betterPow(base: Double, exponent: Int): Double {
    if (exponent == 0) return 1.0

    if (exponent < 0) return betterPow(1 / base, -exponent)

    if (exponent % 2 == 1) return base * betterPow(base, exponent - 1)

    return betterPow(base * base, exponent / 2)
  }
}

Swift

class Solution {
    func betterPow(_ base: Double, _ exponent: Int) -> Double {
        if exponent == 0 { return 1.0 }

        if exponent < 0 { return betterPow(1 / base, -exponent) }

        if exponent % 2 == 1 { return base * betterPow(base, exponent - 1) }

        return betterPow(base * base, exponent / 2)
    }
}

Rust

impl Solution {
    pub fn better_pow(&self, base: f64, exponent: i32) -> f64 {
        if exponent == 0 {
            return 1.0;
        }

        if exponent < 0 {
            return self.better_pow(1.0 / base, -exponent);
        }

        if exponent % 2 == 1 {
            return base * self.better_pow(base, exponent - 1);
        }

        self.better_pow(base * base, exponent / 2)
    }
}

Ruby

class Solution
  def better_pow(base, exponent)
    return 1.0 if exponent == 0

    return better_pow(1.0 / base, -exponent) if exponent < 0

    return base * better_pow(base, exponent - 1) if exponent.odd?

    better_pow(base * base, exponent / 2)
  end
end

Dart

class Solution {
  double betterPow(double base, int exponent) {
    if (exponent == 0) return 1.0;

    if (exponent < 0) return betterPow(1 / base, -exponent);

    if (exponent % 2 == 1) return base * betterPow(base, exponent - 1);

    return betterPow(base * base, exponent ~/ 2);
  }
}

C#

public class Solution {
    public double betterPow(double baseNum, int exponent) {
        if (exponent == 0) return 1.0;

        if (exponent < 0) return betterPow(1 / baseNum, -exponent);

        if (exponent % 2 == 1) return baseNum * betterPow(baseNum, exponent - 1);

        return betterPow(baseNum * baseNum, exponent / 2);
    }
}

PHP

class Solution {
    public function betterPow(float $base, int $exponent): float {
        if ($exponent == 0) {
            return 1.0;
        }

        if ($exponent < 0) {
            return $this->betterPow(1 / $base, -$exponent);
        }

        if ($exponent % 2 == 1) {
            return $base * $this->betterPow($base, $exponent - 1);
        }

        return $this->betterPow($base * $base, intdiv($exponent, 2));
    }
}