Loading…

easyBasicsSometimes asked

Power (Recursion)

Basics · 6 min

Given a base x and non-negative integer exponent n, compute xⁿ recursively.

In plain English

xⁿ = x · xⁿ⁻¹ (linear), or use fast exponentiation: xⁿ = (xⁿ/²)² for O(log n).

Examples

Example 1

Input: x = 2, n = 10
Output: 1024
Note: 2¹⁰.

Example 2

Input: x = 5, n = 0
Output: 1
Note: Anything⁰ = 1.

Example 3

Input: x = 3, n = 3
Output: 27
Note: 3³.

Constraints

0 ≤ n ≤ 30
results fit in 64-bit

Clarifying questions1First question: Non-negative exponent?Explore questions

Q1.Non-negative exponent?
Assuming n ≥ 0; negative n means 1/xⁿ as a double.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Base case `n == 0` returns 1. Linear: `x * power(x, n-1)`. Fast: square `power(x, n/2)` and multiply by x if n is odd → O(log n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know exponentiation by squaring, not just the linear recurrence.

Where candidates slip

Double recursive call, or forgetting the odd ×x.

How to stand out

Generalise to modular exponentiation (take % mod each multiply).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Fast exponentiation

TimeO(log n) fast / O(n) linearSpaceO(log n) stack

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

x^n = x · x^(n-1) is O(n) — can halving the exponent help?

2Hint 2Explore hint

x^n = (x^(n/2))²; compute the half-power only ONCE.

3Hint 3Explore hint

Add a ×x correction when n is odd; base case x⁰ = 1.

A · Core idea

Compute xⁿ recursively. The naive form xⁿ = x · xⁿ⁻¹ is O(n); the smart form is exponentiation by squaring: xⁿ = (x^(n/2))², times an extra x when n is odd — O(log n).

Why squaring is O(log n). Each call halves the exponent (n/2), so the recursion depth is log₂(n). For n = 10⁶ that's ~20 multiplications instead of a million.

Compute the half-power ONCE. The critical detail: store half = power(x, n/2) in a variable and use half*half. Writing power(x,n/2)*power(x,n/2) makes two recursive calls and destroys the speedup, collapsing back to O(n).

The odd correction. When n is odd, n/2 (integer) loses the half-step, so multiply the squared result by an extra x. Base case x⁰ = 1. This squaring trick is the engine behind modular exponentiation in crypto/hashing.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 2, n = 10

n=10

half=power(2,5)

Stateeven

Final result1024

C · Code with teaching comments

solution.javaJava

Fast exponentiation — optimal

2 teaching notes

1
public long power(long x, int n) {
2
    if (n == 0) return 1;
3
    // Compute the half-power once.
4
    long half = power(x, n / 2);
5
    long sq = half * half;
6
    // Square it; multiply by x for odd exponents.
7
    return (n % 2 == 0) ? sq : sq * x;
8
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.8 lines

D · Why it works and complexityO(log n) fast / O(n) linear timeO(log n) stack spaceOpen the invariant and proofExplore the proof

Knowing the O(log n) squaring trick — not just the linear recurrence — is the differentiator here.

ComplexityO(log n) fast / O(n) linear time, O(log n) stack space — halving the exponent each call gives log₂(n) depth with O(1) work per call.

E · Edge cases and pitfalls5x = 5, n = 0 — Base case → 1.Explore edge cases

Edge cases handled

x = 5, n = 0Base case → 1.
x = 3, n = 3Odd correction → 27.
x = 2, n = 10~4 calls, not 10.

Pitfalls

Calling power(x, n/2) twice (loses the O(log n) gain).
Missing the odd-exponent correction.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long power(long x, int n) { if (n == 0) return 1; long half = power(x, n / 2); long sq = half * half; return (n % 2 == 0) ? sq : sq * x;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Recomputing the half-power

power(x,n/2)*power(x,n/2) makes two recursive calls, doubling work each level back to O(n).

Explore the code comparison

Don't write this

return power(x,n/2) * power(x,n/2);   // O(n)

Write this instead

long h = power(x,n/2); return h*h;    // O(log n)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Exponentiation by squaring

Code pattern to memorize

h=power(x,n/2); res = h*h * (n odd ? x : 1)

Rules to remember

1x⁰ = 1.
2Halve the exponent.
3Extra ×x when odd.

Use this pattern when

Fast exponentiation
Modular power

Interview takeaway

Squaring the half-power gives O(log n) exponentiation.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Exponentiation by squaring. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Power of a Number
The iterative binary-exponentiation version.
Pow(x, n)
Coming soon
Handle negative exponents and doubles.

Same pattern

easyBasicsSometimes asked

Power (Recursion)

Basics · 6 min

Given a base x and non-negative integer exponent n, compute xⁿ recursively.

In plain English

xⁿ = x · xⁿ⁻¹ (linear), or use fast exponentiation: xⁿ = (xⁿ/²)² for O(log n).

Examples

Example 1

Input: x = 2, n = 10
Output: 1024
Note: 2¹⁰.

Example 2

Input: x = 5, n = 0
Output: 1
Note: Anything⁰ = 1.

Example 3

Input: x = 3, n = 3
Output: 27
Note: 3³.

Constraints

0 ≤ n ≤ 30
results fit in 64-bit

Clarifying questions1First question: Non-negative exponent?Explore questions

Q1.Non-negative exponent?
Assuming n ≥ 0; negative n means 1/xⁿ as a double.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Base case `n == 0` returns 1. Linear: `x * power(x, n-1)`. Fast: square `power(x, n/2)` and multiply by x if n is odd → O(log n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know exponentiation by squaring, not just the linear recurrence.

Where candidates slip

Double recursive call, or forgetting the odd ×x.

How to stand out

Generalise to modular exponentiation (take % mod each multiply).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Fast exponentiation

TimeO(log n) fast / O(n) linearSpaceO(log n) stack

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

x^n = x · x^(n-1) is O(n) — can halving the exponent help?

2Hint 2Explore hint

x^n = (x^(n/2))²; compute the half-power only ONCE.

3Hint 3Explore hint

Add a ×x correction when n is odd; base case x⁰ = 1.

A · Core idea

Compute xⁿ recursively. The naive form xⁿ = x · xⁿ⁻¹ is O(n); the smart form is exponentiation by squaring: xⁿ = (x^(n/2))², times an extra x when n is odd — O(log n).

Why squaring is O(log n). Each call halves the exponent (n/2), so the recursion depth is log₂(n). For n = 10⁶ that's ~20 multiplications instead of a million.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 2, n = 10

n=10

half=power(2,5)

Stateeven

Final result1024

C · Code with teaching comments

solution.javaJava

Fast exponentiation — optimal

2 teaching notes

1
public long power(long x, int n) {
2
    if (n == 0) return 1;
3
    // Compute the half-power once.
4
    long half = power(x, n / 2);
5
    long sq = half * half;
6
    // Square it; multiply by x for odd exponents.
7
    return (n % 2 == 0) ? sq : sq * x;
8
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.8 lines

D · Why it works and complexityO(log n) fast / O(n) linear timeO(log n) stack spaceOpen the invariant and proofExplore the proof

Knowing the O(log n) squaring trick — not just the linear recurrence — is the differentiator here.

ComplexityO(log n) fast / O(n) linear time, O(log n) stack space — halving the exponent each call gives log₂(n) depth with O(1) work per call.

E · Edge cases and pitfalls5x = 5, n = 0 — Base case → 1.Explore edge cases

Edge cases handled

x = 5, n = 0Base case → 1.
x = 3, n = 3Odd correction → 27.
x = 2, n = 10~4 calls, not 10.

Pitfalls

Calling power(x, n/2) twice (loses the O(log n) gain).
Missing the odd-exponent correction.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long power(long x, int n) { if (n == 0) return 1; long half = power(x, n / 2); long sq = half * half; return (n % 2 == 0) ? sq : sq * x;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Recomputing the half-power

power(x,n/2)*power(x,n/2) makes two recursive calls, doubling work each level back to O(n).

Explore the code comparison

Don't write this

return power(x,n/2) * power(x,n/2);   // O(n)

Write this instead

long h = power(x,n/2); return h*h;    // O(log n)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Exponentiation by squaring

Code pattern to memorize

h=power(x,n/2); res = h*h * (n odd ? x : 1)

Rules to remember

1x⁰ = 1.
2Halve the exponent.
3Extra ×x when odd.

Use this pattern when

Fast exponentiation
Modular power

Interview takeaway

Squaring the half-power gives O(log n) exponentiation.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Exponentiation by squaring. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Power of a Number
The iterative binary-exponentiation version.
Pow(x, n)
Coming soon
Handle negative exponents and doubles.

Same pattern