Calculate Power Using Recursion in Java
Problem
Computing a power recursively means expressing base^exponent in terms of a smaller instance of the same problem, until a base case is reached.
Given a base and an exponent, compute the result using recursion.
Java Program
public class PowerRecursive {
static long power(int base, int exponent) {
if (exponent == 0) return 1; // base case: anything to the power 0 is 1
return base * power(base, exponent - 1);
}
public static void main(String[] args) {
int base = 2, exponent = 10;
System.out.println(base + "^" + exponent + " = " + power(base, exponent));
}
}Output
Core Logic
Peeling off one multiplication per recursive call, and stopping once the exponent reaches zero, maps the mathematical definition of a power directly onto code.
- 1The base case
if (exponent == 0) return 1;stops the recursion, since anything to the power of 0 is 1. - 2Every other call returns
base * power(base, exponent - 1), deferring its own result until the smaller call finishes. - 3Each call reduces the exponent by exactly 1, so the recursion descends one level per remaining multiplication needed.
- 4As the calls return, the pending multiplications unwind back up the stack, building the final result.
power(2, 10) unwinds through power(2, 9), power(2, 8), and so on down to the base case, multiplying by 2 at each level on the way back up to reach 1024.Key Point: This is a direct, one-multiplication-per-call recursion — straightforward to follow, but it makes exactly as many recursive calls as the exponent itself.
Why: Each call peels off one multiplication and recurses on a smaller exponent, so both the number of calls and the stack depth grow linearly with the exponent.
Key Concepts
Approach 2: Fast Exponentiation (Squaring)
public class PowerFastRecursive {
static long power(int base, int exponent) {
if (exponent == 0) return 1;
long half = power(base, exponent / 2);
if (exponent % 2 == 0) {
return half * half; // base^n = (base^(n/2))^2 for even n
} else {
return base * half * half; // one extra factor of base for odd n
}
}
public static void main(String[] args) {
int base = 2, exponent = 10;
System.out.println(base + "^" + exponent + " = " + power(base, exponent));
}
}
Output
Core Logic
Since base^n equals (base^(n/2))² whenever n is even, halving the exponent at every step reaches the base case in far fewer calls than counting down by 1 each time.
- 1Each call first recurses on
exponent / 2, computinghalf— the result for roughly half the original exponent. - 2If
exponentis even, the answer is simplyhalf * half, matching the identitybase^n = (base^(n/2))². - 3If
exponentis odd, one extra factor ofbaseis needed:base * half * half, to account for the leftover power that halving couldn't evenly split. - 4The same base case,
exponent == 0, still stops the recursion.
power(2, 10) only needs to resolve exponent values 10, 5, 2, 1, 0 — five calls deep — instead of the ten levels the naive version needs.Key Point: Halving the exponent instead of decrementing it is what turns a linear number of calls into a logarithmic one — the same kind of speedup fast-doubling gives Fibonacci.
Why: Each call halves the exponent instead of decrementing it by one, so the recursion depth — and the total number of calls — grows logarithmically with n.