Power Function - Naive Recursion

The obvious recursive formula is $x^n = x \times x^{n-1}$. Base case: $x^0 = 1$. This is correct and simple. To compute $x^{10}$, you compute $x^9$ and multiply by $x$. To compute $x^9$, you compute $x^8$ and multiply by $x$. And so on.

This works, but it makes $n$ recursive calls. For $x^{1000}$, that is $1000$ calls. Can you do better? Take time to work through examples. Notice what happens when $n$ is even: $x^{10} = (x^5)^2$.