Divide and Conquer to find a power
The algorithm relies on two facts:


If $n$ is even, $n=2k$, we have $a^n = a^{2k}=a^ka^k = a^{n/2}a^{n/2} = (a^{n/2})^2$
If $n$ is odd, $n=2k+1$, we have $a^n=a^{2k+1}=a^1a^{2k}=a(a^ka^k)=a(a^{(n-1)/2})^2$


In other words, we have
$$
a^n=\begin{cases}
(a^{\lfloor n/2 \rfloor})^2 &amp;\text{if $n$ is even}\\
a(a^{\lfloor n/2 \rfloor})^2 &amp;\text{if $n$ is odd}
\end{cases}
$$
You've computed $pow(a, n)$ by changing it to a problem involving an instance of the half-sized problem $pow(a, n/2)$ along with a squaring and possibly a multiplication by $a$.