Power Function

Write a recursive function power(x, n) that calculates $x^n$. Input: $x = 2, n = 10$ → Output: 1024. You must use recursion and must not use the ** operator. Naive multiplication is $O(N)$ — achieve $O(\log N)$.

Exponentiation by squaring: $x^n = (x^{n/2})^2$ when $n$ is even. This halves the problem at each step, giving $O(\log N)$. For odd $n$: $x^n = x \cdot (x^{\lfloor n/2 \rfloor})^2$. This mirrors the binary search halving principle, applied to computation.

1. Base case: if $n = 0$, return 1 (by definition $x^0 = 1$).
2. Recursively compute $\text{half} = \text{power}(\text{base}, \lfloor n/2 \rfloor)$.
3. If $n$ is even: return $\text{half}^2$.
4. If $n$ is odd: return $\text{base} \times \text{half}^2$.

• Using a simple loop ($x \times x \times \cdots$, $n$ times) — $O(N)$, too slow for $n = 10^6$
• Computing power(base, exp // 2) twice instead of storing the result — turns $O(\log N)$ into $O(N)$
• Not handling $n = 0$ as the base case
• Forgetting the odd exponent case: $x^5 = x \cdot (x^2)^2$, not just $(x^2)^2$

Fast exponentiation (binary exponentiation) reduces $10^6$ multiplications to about 20. It underpins modular exponentiation in RSA cryptography, matrix exponentiation for Fibonacci, and competitive programming. "Compute half, then combine" is the essence of divide and conquer.