Problem Statement

Write a Recursive Approach to Calculate Power of Integer to N Pow(x,n).

Given an integer x and an integer n, write a recursive function to calculate the power of x to the nth power.

Example

Constraints:

• -100.0 < x < 100.0
• -2³¹ <= n <= 2³¹-1
• n is an integer.
• Either x is not zero or n > 0.
• -10⁴ <= xⁿ <= 10⁴

Solution

To calculate the power of x to the nth power recursively, we can follow these steps:

1. If n is equal to 0, return 1 since any number raised to the power of 0 equals 1.
2. If n is less than 0, return 1 divided by the result of calculating x raised to the power of -n.
3. If n is greater than 0, recursively calculate x raised to the power of n/2. Store the result in a variable temp.
4. If n is even, return the square of temp (i.e., temp * temp).
5. If n is odd, return x multiplied by the square of temp (i.e., x * temp * temp).

This approach works by dividing the power n into smaller subproblems, reducing the number of recursive calls. By utilizing the property that x^(2k) is equal to (x^k)^2, we can optimize the computation and reduce the time complexity.

Code

Here is the code for this algorithm: