Power Function

Problem Statement

Write a Java program that implements both recursive and iterative methods to compute (x^n), where (x) is a double and (n) is a non-negative integer representing the power. The program should return the result of (x) raised to the power (n) and test the methods with different inputs, including edge cases like (n = 0) and (n = 1). Analyze the space complexity of both approaches. You can visualize this as calculating the total area of a square piece of land ((x)) that is scaled by itself (n) times, either by repeatedly multiplying (iterative) or by breaking it into smaller multiplications (recursive).

Input: A double (x) and a non-negative integer (n) (e.g., (x = 2.0, n = 3)). Output: A double representing (x^n) (e.g., 8.0 for (2.0^3)). Constraints:

• (-100.0 \leq x \leq 100.0).
• (0 \leq n \leq 10^3).
• The result should fit within a double’s precision. Example:
• Input: (x = 2.0, n = 3)
• Output: 8.0
• Explanation: (2.0^3 = 2.0 * 2.0 * 2.0 = 8.0).
• Input: (x = 5.0, n = 0)
• Output: 1.0
• Explanation: Any non-zero number raised to the power 0 is 1.

Pseudocode

FUNCTION recursivePower(x, n)
    IF n equals 0 THEN
        RETURN 1.0
    ENDIF
    IF n equals 1 THEN
        RETURN x
    ENDIF
    RETURN x * recursivePower(x, n - 1)
ENDFUNCTION

FUNCTION iterativePower(x, n)
    IF n equals 0 THEN
        RETURN 1.0
    ENDIF
    SET result to 1.0
    FOR i from 1 to n
        SET result to result * x
    ENDFOR
    RETURN result
ENDFUNCTION

Algorithm Steps

1. For the recursive approach: a. Check if (n) is 0. If so, return 1.0, as any non-zero number raised to the power 0 is 1. b. Check if (n) is 1. If so, return (x), as (x^1 = x). c. Define a recursive function that multiplies (x) by the result of the recursive call for (n - 1). d. Return the computed result.
2. For the iterative approach: a. Check if (n) is 0. If so, return 1.0. b. Initialize a variable result to 1.0. c. Iterate (n) times, multiplying result by (x) in each iteration. d. Return the final result.
3. Test both methods with various inputs (e.g., (n = 0, 1, 5)) and analyze space complexity.

Java Implementation

public class PowerFunction {
    // Computes x^n using recursion
    public double recursivePower(double x, int n) {
        // Base case: x^0 = 1
        if (n == 0) {
            return 1.0;
        }
        // Base case: x^1 = x
        if (n == 1) {
            return x;
        }
        // Recursive case: x * x^(n-1)
        return x * recursivePower(x, n - 1);
    }

    // Computes x^n using iteration
    public double iterativePower(double x, int n) {
        // Base case: x^0 = 1
        if (n == 0) {
            return 1.0;
        }
        // Initialize result
        double result = 1.0;
        // Multiply x by itself n times
        for (int i = 1; i <= n; i++) {
            result *= x;
        }
        // Return final result
        return result;
    }
}

Output

For the input (x = 2.0, n = 3), both methods output:

8.0

Explanation: (2.0^3 = 2.0 * 2.0 * 2.0 = 8.0).

For the input (x = 5.0, n = 0), both methods output:

1.0

Explanation: Any non-zero number raised to the power 0 is 1.

For the input (x = 3.0, n = 2), both methods output:

9.0

Explanation: (3.0^2 = 3.0 * 3.0 = 9.0).

How It Works

• Recursive Approach:
  • Step 1: The recursivePower method checks if (n = 0). For (x = 2.0, n = 3), it proceeds to recursion.
  • Step 2: Recursion:
    • For (n = 3): Returns (2.0 * recursivePower(2.0, 2)).
    • For (n = 2): Returns (2.0 * recursivePower(2.0, 1)).
    • For (n = 1): Base case, returns 2.0.
    • Unwind: (2.0 * (2.0 * 2.0) = 2.0 * 4.0 = 8.0).
  • Example Trace: For (x = 2.0, n = 3), computes (2.0 * (2.0 * (2.0 * 1)) = 8.0).
• Iterative Approach:
  • Step 1: The iterativePower method checks if (n = 0). For (x = 2.0, n = 3), it initializes result = 1.0.
  • Step 2: Iterates 3 times:
    • Iteration 1: result = 1.0 * 2.0 = 2.0.
    • Iteration 2: result = 2.0 * 2.0 = 4.0.
    • Iteration 3: result = 4.0 * 2.0 = 8.0.
  • Example Trace: For (x = 2.0, n = 3), multiplies (2.0 * 2.0 * 2.0 = 8.0).
• Space Complexity Analysis:
  • Recursive: O(n) due to the call stack, which grows linearly with (n).
  • Iterative: O(1), as it uses only a single variable for the result.
  • The iterative approach is more space-efficient, especially for large (n), while both have similar time performance for this basic implementation.

Complexity Analysis Table

Note:

• n is the exponent.
• Time complexity: O(n) for both, as recursive makes n calls, and iterative performs n multiplications.
• Space complexity: O(n) for recursive due to the call stack; O(1) for iterative, using only a single variable.
• Best, average, and worst cases are O(n) for both.

✅ Tip: Use the iterative approach for large (n) to avoid stack overflow and minimize space usage. Test with edge cases like (n = 0), (n = 1), and large (n) (e.g., 1000) to verify correctness and compare space efficiency.

⚠ Warning: The recursive approach may cause stack overflow for very large (n) due to O(n) space complexity. Be cautious with floating-point precision for large (x) or (n), as results may exceed double’s capacity.