Lessons from Power (Summary)

$1.$ Halving the problem size at each step gives $O(\log n)$ time.

$2.$ Squaring a value lets you compute powers exponentially faster than repeated multiplication.

$3.$ Recursive solutions create call stacks of depth $O(\log n)$, which you can eliminate with iteration if space matters.