Problem. Implement my_pow(x, n) = xⁿ for a float x and an integer n, which can be negative and as large as
2³¹ − 1 in absolute value.
my_pow(2.0, 10) → 1024.0
my_pow(2.1, 3) → 9.261
my_pow(2.0, -2) → 0.25
The recursion tree here isn't a wide search tree but a single chain that halves the problem at each level: the cheapest kind of recursion, and a pattern that works for anything you can multiply associatively.
ML context. Repeated multiplication by the same thing is everywhere: the n-step transition probabilities of a Markov chain are the n-th power of its matrix, a linear recurrence is a matrix power, decayed learning rates and exponential moving averages use γⁿ, and modular exponentiation underlies hashing and cryptography. And multiplying many small probabilities is where floats break, which is why models work in log space (Change D).