Power of a number using recursion

Given a number x and an integer exponent n, return the value of x raised to the power n using recursion.

Approach 1

A power can be written in terms of a smaller power.

For example:

2⁴ = 2 × 2³

2³ = 2 × 2²

In general:

xⁿ = x × xⁿ⁻¹

Each recursive call reduces the exponent by 1. When the exponent reaches 0, no more multiplication is required because any non-zero number raised to the power 0 is 1.

While the recursive calls return, each call multiplies the value returned by the smaller call with x. In this way, the final power is gradually built.

Algorithm

• Define a recursive function that receives x and n, where n represents the remaining exponent.

• When n == 0, return 1, because any number raised to the power 0 is 1.

• For n > 0, recursively calculate the value of x^n-1.

• Multiply the returned value by x and return the result, allowing each recursive call to contribute one factor of x.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), because the exponent decreases by 1 in every recursive call.

Space Complexity: O(N), because the recursion creates one call-stack frame for each value of the exponent.

Approach 2

The previous approach reduces the exponent by only 1 in every recursive call. We can reduce the number of calls by dividing the exponent approximately in half.

For an even exponent:

x⁸ = x⁴ × x⁴

Both halves are identical, so x⁴ only needs to be calculated once. Its result can then be multiplied by itself.

In general:

xⁿ = xⁿ⁄² × xⁿ⁄²

For an odd exponent, one factor of x remains after dividing the exponent into two equal integer parts.

For example:

x⁷ = x × x³ × x³

So the recursive function calculates the power for n / 2 only once and stores it. The stored value is squared for an even exponent, while an additional factor of x is multiplied for an odd exponent.

Since the exponent is reduced approximately by half in every recursive call, the number of recursive calls becomes logarithmic.

Algorithm

• Define a recursive function that receives x and n, where n represents the remaining exponent.

• When n == 0, return 1, because any number raised to the power 0 is 1.

• For n > 0, recursively calculate the value of x^n-1.

• Multiply the returned value by x and return the result, allowing each recursive call to contribute one factor of x.

Dry Run

Solution

Complexity Analysis

Time Complexity:O(log N), because the exponent is reduced approximately by half in every recursive call.

Space Complexity: O(log N), because the recursion depth is proportional to the number of times the exponent can be halved.

FAQs

Q1. What happens when n = 0?

The recursion immediately reaches the base case and returns 1, because (x⁰ = 1).

Q2. Why does the base case return 1 when n = 0?

1 is the neutral value for multiplication. It allows the pending recursive multiplications to continue without changing their result.

Q3. Why is halfPower stored instead of calling the function twice?

Calling power(x, n / 2) twice would repeat the same work. Storing it once keeps the optimized approach logarithmic.

Q4. Why is an extra x multiplied when the exponent is odd?

An odd exponent cannot be divided into two equal integer halves. After forming two copies of x^(n/2), one factor of x is still left, so it must be included separately.

Q5. Why does the optimized approach call the recursive function only once for n / 2?

Both halves require the same value (xⁿ_/2). Calculating it once and reusing it prevents repeated recursive work and keeps the time complexity logarithmic.

Q6. Which recursive approach is preferred for large exponents?

Binary exponentiation is preferred because it reduces the exponent by half in every call, taking O(log |N|) time instead of O(|N|).