Power Function - Implementation

Here is the faster recursive power function:

function power(x, n)
    if n = 0 then
        return 1
    if n is even then
        half := power(x, n / 2)
        return half × half
    return x × power(x, n - 1)

If $n$ is $0$, return $1$. If $n$ is even, compute power(x, n / 2) once, store it, and square it. If $n$ is odd, multiply $x$ by power(x, n - 1). Trace power(2, 10): you get power(2, 5) squared. Then power(2, 5) = $2$ × power(2, 4). Then power(2, 4) = power(2, 2) squared. Then power(2, 2) = power(2, 1) squared. Then power(2, 1) = $2$ × power(2, 0) = $2$. Just $6$ calls for $n = 10$.

Time complexity: $O(\log n)$.

Space complexity: $O(\log n)$ due to the recursive call stack.