Algorithm

Power(x, n)

Recursion Pattern

Power(x, n)

Given a number x and a non-negative integer exponent n, compute x raised to the power n (x^n). Return the result. The interesting version is not the obvious O(n) multiply-n-times approach but an O(log n) recursion that halves the exponent each step — a first taste of divide and conquer.

CONSTRAINTS
  • 0 <= n <= 2³¹ − 1 (the fast version must handle large exponents)
  • x is a real number
  • x⁰ = 1 for any x
EXAMPLE 1
Input: x = 2, n = 0
Output: 1
Any value to the power 0 is 1. Base case — no multiplication.
EXAMPLE 2
Input: x = 2, n = 10
Output: 1024
2¹⁰ = 1024, reached in about log₂(10) ≈ 4 levels of halving.
EXAMPLE 3
Input: x = 3, n = 4
Output: 81
3⁴ = (3²)² = 9² = 81. Even exponents are perfect squares of the half.
EXAMPLE 4
Input: x = 2, n = 7
Output: 128
2⁷ = 2 × (2³)² = 2 × 64 = 128. The odd exponent needs one extra factor of x after squaring.
Why halve the exponent instead of subtracting one?
Subtracting one gives O(n) multiplications; halving gives O(log n), because the exponent reaches 0 in about log₂ n steps. For large n that is the difference between a billion operations and thirty.
How are odd exponents handled?
x^n for odd n is not a perfect square, so peel one factor: x^n = x × (x^(n/2))², using integer division for n/2. The squared half plus one extra x gives the answer.
Why must half be stored in a variable?
So the recursion is called only once. Calling power(x, n//2) twice rebuilds a branching call tree and destroys the O(log n) benefit — bind it once and square the stored value.
What about negative exponents?
This version assumes n ≥ 0. Negative n is handled by computing the positive power and returning its reciprocal (1 / result) — a small wrapper around the same recursion.

Raising x to the power n means multiplying x by itself n times. The naive recursion is linear and obvious; the point of this problem is to make it logarithmic by halving the exponent, which introduces divide and conquer — the recursive idea underneath merge sort and binary search.

The linear way, and its waste

The definition x^n = x × x^(n−1) gives an immediate linear recursion (or loop): peel one factor of x, recurse on n − 1.

python
def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n - 1)   # n multiplications, depth n

Correct, but it makes n multiplications and stacks n frames deep. For n up to about two billion, that is far too slow and would overflow the stack. The waste: we are shrinking the exponent by 1 each time when we could shrink it by half.

The reframe: square the half

Exponents split by addition, and that means powers split by multiplication: x^n = x^(n/2) × x^(n/2). So if we know half = x^(n/2), we get x^n by squaring it — one multiplication instead of n. Compute half once (not twice — that would rebuild the exponential tree of naive Fibonacci), then square it. The only wrinkle is odd exponents: x^7 is not a clean square, so peel one factor first — x^7 = x × (x^3)². In code:

python
def power(x, n):
    if n == 0:                       # base case
        return 1
    half = power(x, n // 2)          # ONE recursive call, exponent halved
    if n % 2 == 0:
        return half * half           # even: perfect square
    return half * half * x           # odd: square, then one extra x
Why this is O(log n)

Each call halves the exponent, so the exponent goes n → n/2 → n/4 → … → 1 → 0. The number of halvings to reach the base is about log₂ n. That is the entire depth of the recursion and the total number of multiplications — O(log n) time and O(log n) stack. For n = 1,000,000,000 the linear version needs a billion multiplications; this one needs about 30. Halving instead of decrementing is the whole win.

Worked Example:power(2, 10)
- power(2, 10): half = power(2, 5). Waits.
- power(2, 5): half = power(2, 2). Waits.
- power(2, 2): half = power(2, 1). Waits.
- power(2, 1): half = power(2, 0) = 1. n is odd → 1 × 1 × 2 = 2. Return 2.
- Unwind: power(2,2): 2 is even → 2 × 2 = 4. power(2,5): 5 is odd → 4 × 4 × 2 = 32. power(2,10): 10 is even → 32 × 32 = 1024.
- Five levels of recursion (≈ log₂ 10) produce 2¹⁰ = 1024.
Crucial Notecompute half once and reuse it. Writing power(x, n//2) power(x, n//2) looks equivalent but calls the recursion twice*, rebuilding a doubling call tree and dragging you right back to O(n) (in fact worse). Binding the single result to a variable is what keeps the tree a straight logarithmic chain — the same "don't recompute what you already have" discipline as memoization, achieved here structurally.
The pattern, extracted

This is divide and conquer: split the problem into a much smaller sub-problem (here, half the exponent), solve it recursively, and combine the result cheaply (square it). The signal to reach for it is a problem where solving a half-sized input gets you most of the way to the full answer — the hallmark that produces O(log n) or O(n log n) algorithms. You will meet the same shape in Binary Search (discard half the array each step) and Merge Sort (sort two halves, then merge). Recognizing "can I halve this?" is the reflex this problem trains.

O(n) Linear Recursion
→
O(log n) Time · O(log n) Stack Fast Exponentiation