Recursion
Halve the work: exponentiation
Why it matters
Large powers appear in cryptography, numerical models, and graphics, where an exponent may be in the billions. Multiplying once for every unit of the exponent makes an otherwise small calculation unusable, even though the result has strong repeated structure. The calculation must handle n near 2³¹ without performing n multiplications or using n stack frames.
Example
Pow(x, n)
Implement pow(x, n) — x raised to the integer power n — with O(log |n|) recursive calls. Handle negative exponents.
- Input
- x = 2.0, n = 10
- Output
- 1024.0
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Pow(x, n)
x = 2.0, n = 10→1024.0
The baseline, Multiply n times, is O(n) · O(1). The better model below keeps this exact input and removes that bottleneck.
For x = 2.0 and n = 10, the brute loop multiplies ten times. Ask once for 2⁵, square it to get 2¹⁰, and keep halving the exponent; the number of calls follows its bits instead of its magnitude.
For x = 2.0 and n = 10, calls use exponents 10 → 5 → 2 → 1 → 0. The base call returns 1.0. Each waiting call stores that single result in half before combining it, so the smaller power is never computed twice.
On return, n = 1 is odd, so it gives 1 × 1 × 2 = 2. n = 2 gives 2 × 2 = 4; n = 5 gives 4 × 4 × 2 = 32; n = 10 gives 32 × 32 = 1024.0. A negative n first reciprocates the corresponding positive power.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.