Power Function using recursion in Java

Power Function using recursion in Java

Problem

We want to compute: ab=a×a×a…  (b times)a^b = a \times a \times a \dots \; (b \text{ times})

For example:

  • 25=322^5 = 32
  • 34=813^4 = 81

Recursive Idea

  1. Base case:
    • If b=0b = 0, return 1 (since a0=1a^0 = 1).
  2. Recursive case:
    • ab=a×a(b−1)a^b = a \times a^{(b-1)}.

Simple Recursive Code

public class PowerRecursion {
    // Recursive method to calculate a^b
    public static int power(int a, int b) {
        if (b == 0) {
            return 1; // Base case
        }
        return a * power(a, b - 1); // Recursive case
    }

    public static void main(String[] args) {
        int base = 2, exponent = 5;
        int result = power(base, exponent);
        System.out.println(base + "^" + exponent + " = " + result);
    }
}

Output

2^5 = 32

Optimized Version (Fast Exponentiation)

We can make it faster using divide and conquer:

  • If b is even: ab=(ab/2)2a^b = (a^{b/2})^2
  • If b is odd: ab=a×(ab−1)a^b = a \times (a^{b-1})
public class FastPowerRecursion {
    public static int power(int a, int b) {
        if (b == 0) return 1;
        
        int halfPower = power(a, b / 2);
        
        if (b % 2 == 0) {
            return halfPower * halfPower;
        } else {
            return a * halfPower * halfPower;
        }
    }

    public static void main(String[] args) {
        int base = 2, exponent = 10;
        int result = power(base, exponent);
        System.out.println(base + "^" + exponent + " = " + result);
    }
}

Output (Optimized Version)

2^10 = 1024

⚡ The optimized version reduces complexity from O(b) to O(log b).

Leave a Reply