32 calls for INT_MAX. Naive recursion needs 2.1 billion.
Halving n drops its lowest binary digit, and n & 1 is that digit. So fast exponentiation reads n in binary: right to left on the way down, then builds xn from the 1-bits on the way back up.
Press Next to make the first call.
On the way down, each call looks at the lowest bit of n and drops it. An even n owes nothing; an odd n owes one factor of its current base, and that debt is only paid when the frame returns. The base squares at every level, so the frame reading bit i is holding x2i.
On the way back up, the frames return highest bit first, and every 1-bit multiplies its base in. Step through 10 and watch bits 1 and 3 light up: x2 × x8 = x10. The answer is assembled from the binary representation of n, in the opposite order to how it was read.
The recursion is reading n in binary. That is the whole reason it is O(log n).
| n | naive calls | fast calls | binary digits |
|---|---|---|---|
| 10 | 11 | 5 | 4 |
| 1,000,000 | 1,000,001 | 21 | 20 |
| 109 | 1,000,000,001 | 31 | 30 |
| INT_MAX | 2,147,483,648 | 32 | 31 |
Fast calls are always binary digits plus one, for the base case. A number n has about log2 n digits, so that is the cost. At INT_MAX the naive version does not merely run slowly: 2.1 billion frames is far more than any default stack holds, so it overflows long before it finishes.
Load INT_MIN. Its binary is a 1 followed by thirty-one 0s, so every frame on the way down is even and owes nothing, until the last. It also takes one extra frame, the negative wrapper, for 34 calls in all.
That wrapper negates n. -(-231) = 231 does not fit in an int, so negating it as one is signed overflow. The solution takes long long n, which widens the value at the call boundary so -1 * n runs in 64 bits. Order matters: (long long)(-n) would still overflow, because the negation runs before the cast.