Coding Exercise: Calculate Power (x^n) Using Recursion

Write recursive function to compute x^n where x^0=1, x^n=x*x^(n-1).

Test cases: power(2,3)=8, power(3,2)=9, power(5,0)=1.

Problem Statement

Input: base x, exponent n (n ≥ 0)

Output: x^n

Base case: power(x,0) = 1

Recursive: power(x,n) = x * power(x,n-1)

Approach

1. If n==0, return 1 (base case)

2. Else: return x * power(x, n-1)

3. Linear recursion (much better than Fibonacci!)

Solution Code

              
            
C++

            #include <iostream>
using namespace std;

long long power(int base, int exp) {
    // Base case
    if (exp == 0) {
        return 1;
    }
    // Recursive case
    return base * power(base, exp - 1);
}

int main() {
    int x, n;
    cout << "Enter base: ";
    cin >> x;
    cout << "Enter exponent: ";
    cin >> n;
    
    cout << x << "^" << n << " = " << power(x, n) << endl;
    return 0;
}
          

Dry Run: power(3, 4)

              
            
TEXT

            power(3,4) → 3 * power(3,3)
           ↓
power(3,3) → 3 * power(3,2)
           ↓
power(3,2) → 3 * power(3,1)
           ↓
power(3,1) → 3 * power(3,0)
           ↓
power(3,0) → 1 (BASE CASE)

Unwind: 3*1=3 → 3*3=9 → 3*9=27 → 3*27=81
Result: 81 ✓
          

Test Cases

Optimization: Exponentiation by Squaring

              
            
C++

            long long powerFast(int base, int exp) {
    if (exp == 0) return 1;
    if (exp % 2 == 0) {
        long long half = powerFast(base, exp/2);
        return half * half;
    }
    return base * powerFast(base, exp-1);
}
          

Time: O(log n) vs O(n)

Complexity Analysis

Basic: Time O(n), Space O(n)

Optimized: Time O(log n), Space O(log n)

Practice Variations

1. power(x, n) for negative exponents (1/x^n)

2. Iterative power function

3. Binary exponentiation implementation

Conclusion

Mastered recursive power! Linear recursion is intuitive.

Next: String reversal or array sum recursively.