Power Function - Walkthrough

Let me trace power($2$, $10$):

Call $1$: power($2$, $10$) $\rightarrow$ $10$ is even, so compute power($2$, $5$) and square it Call $2$: power($2$, $5$) $\rightarrow$ $5$ is odd, so return $2 \times$ power($2$, $4$)

Call $3$: power($2$, $4$) $\rightarrow$ $4$ is even, so compute power($2$, $2$) and square it Call $4$: power($2$, $2$) $\rightarrow$ $2$ is even, so compute power($2$, $1$) and square it Call $5$: power($2$, $1$) $\rightarrow$ $1$ is odd, so return $2 \times$ power($2$, $0$)

Call $6$: power($2$, $0$) hits base case, returns $1$

Then the results come back: $2 \times 1 = 2$, $2^2 = 4$, $4^2 = 16$, $2 \times 16 = 32$, $32^2 = 1024$. Only $6$ calls instead of $10$ multiplications.