Raising x to the power n means multiplying x by itself n times, so 2^10 is 2 x 2 x ... x 2 with ten factors, which equals 1024. The exponent 0 is a special anchor: x^0 is defined as 1 for any base, because multiplying no factors together leaves the multiplicative identity.

The exponent gives the recursion its structure. One relationship is x^n = x x x^(n-1), which peels off a single factor at a time. A sharper relationship is x^n = (x^(n/2))^2, which cuts the exponent in half at each step. Both lead to recursive solutions, but the halving version reaches the answer in far fewer multiplications.

Key Constraints:

Intuition

Compute x^(n/2) once, then square it to get x^n. That single multiplication does the work of an entire half of the exponent.

Odd exponents need one adjustment. When n is odd, integer division n / 2 rounds down, so squaring x^(n/2) gives x^(n-1), which is short by one factor of x. Multiply that extra x back in. For example, x^5 is (x^2)^2 x x, where (x^2)^2 is x^4 and the trailing x completes the fifth factor.

The base case is power(x, 0) = 1, the empty product. Each call halves the exponent, reaching the base case in about log2(n) steps rather than n.

Algorithm

Example Walkthrough

Input:

To find power(2, 10), the call needs power(2, 5) and will square it. power(2, 5) needs power(2, 2), which needs power(2, 1), which needs power(2, 0) = 1. Now the values unwind. power(2, 1) has an odd exponent, so it returns 1 x 1 x 2 = 2. power(2, 2) is even, so it returns 2 x 2 = 4. power(2, 5) is odd, so it returns 4 x 4 x 2 = 32. Finally power(2, 10) is even, so it returns 32 x 32 = 1024. The exponent went 10, 5, 2, 1, 0, only five levels deep, which is why halving is so much faster than peeling one factor at a time.

Code

Intuition

A loop expresses x^n without recursion. Start an accumulator at 1, then multiply by x exactly n times. After the last multiplication, the accumulator holds x^n. Starting at 1 also returns the correct answer for n = 0, since the loop runs zero times and leaves the accumulator unchanged.

This version is simpler to reason about, but it does n multiplications instead of about log2(n), so it is slower for large exponents.

Algorithm

Example Walkthrough

Input:

The accumulator starts at 1. Multiplying by 2 ten times produces 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. After the tenth multiplication the loop stops and returns 1024, the same answer the halving version found. The difference is the work: this loop performed ten multiplications, while the recursive halving used only a handful.

Code