Power Function - The Optimization

Here is the trick: $x^{10} = (x^5)^2$. Instead of $10$ multiplications, compute $x^5$ once and square it. More generally: if $n$ is even, $x^n = (x^{n/2})^2$. If $n$ is odd, $x^n = x \times x^{n-1}$. This cuts the problem size in half each time (when $n$ is even).

Instead of $O(n)$ calls, you make $O(\log n)$ calls. For $n = 1000$, that is $16$ calls instead of $1000$. Huge difference. This improvement reduces redundant work largely.