basics · beginner · ~15 min
Recursive base + smaller subproblem with O(log n) depth.
Implement long ipow(int base, int exp) recursively. exp >= 0. Use the binary-exponentiation trick: ipow(b, e) = (e is even ? ipow(b*b, e/2) : b * ipow(b, e-1)).
A clean recursive function is the entry point to dynamic programming. Doing power as iterate-vs-recurse is the cleanest example.
base and non-negative exp.
base^exp as long.
Must be recursive.
long ipow(int base, int exp) { /* TODO */ return 0; }
Stack overflow at large exp if you do the naïve linear recursion.
exp == 0 → 1. base == 0, exp == 0 → 1 (convention).
O(log exp).
Solve this exercise in the browser editor — compile and run against the test harness, no setup required.