M power N Using Recursive function

This is one of the example of using recursive function in Java to find M power N (M^N).

Recursive Approach

The recurrence relation is straightforward: M^N = M * M^(N-1), with a base case that stops the recursion once N reaches 0.

public class MPowerN {

	public static int pow(int m, int n) {
		if (n == 0) {
			return 1;
		}
		return m * pow(m, n - 1);
	}

}

@Test
public void test() {
    assertEquals(pow(2, 3), 8);
    assertEquals(pow(5, 0), 1);
    assertEquals(pow(7, 1), 7);
}

Watch the base case. It’s tempting to write the base case as n > 1 (returning m once n reaches 1) instead of n == 0 (returning 1). That version happens to work for n >= 1, but it silently returns the wrong answer for pow(m, 0) — mathematically any number raised to the power of 0 is 1, not m. Always trace the base case against n = 0 before trusting a power function.

Tracing pow(2, 3) shows how the calls unwind:

pow(2, 3) = 2 * pow(2, 2)
          = 2 * (2 * pow(2, 1))
          = 2 * (2 * (2 * pow(2, 0)))
          = 2 * (2 * (2 * 1))
          = 8

Each call does one multiplication and recurses once, so this makes N recursive calls — time complexity is 𝘖(n), and space complexity is also 𝘖(n) since each pending call stays on the call stack until the base case returns.

Optimized Recursive Approach (Fast Exponentiation)

We can cut the number of recursive calls from N down to log₂N by halving the exponent at every step instead of decrementing it by 1. This relies on two identities:

• If N is even: M^N = (M^(N/2))^2
• If N is odd: M^N = M * (M^(N/2))^2

public class MPowerNFast {

	public static long pow(long m, int n) {
		if (n == 0) {
			return 1;
		}
		long half = pow(m, n / 2);
		if (n % 2 == 0) {
			return half * half;
		}
		return m * half * half;
	}

}

@Test
public void testFastPow() {
    assertEquals(pow(2, 10), 1024);
    assertEquals(pow(3, 5), 243);
    assertEquals(pow(5, 0), 1);
}

This is the same technique used internally by Math.pow()-style implementations and is a common interview follow-up once you’ve shown the naive 𝘖(n) version — halving the exponent brings the time complexity down to 𝘖(log n).

A couple of things to keep in mind if you extend this further: the result type is long here rather than int, since repeated squaring grows the result much faster than the naive version and overflows sooner; and this implementation only handles non-negative exponents — supporting negative N would mean returning 1.0 / pow(m, -n) as a double instead.