Power - Implementation

Here's the full solution using recursion:

function pow(x, n)
    if n = 0 then
        return 1
    if n < 0 then
        return 1 / pow(x, -n)
    if n is even then
        half := pow(x, n / 2)
        return half * half
    else
        return x * pow(x, n - 1)

The recursion depth is $O(\log n)$ because you halve $n$ at each step. Total time: $O(\log n)$. Space: $O(\log n)$ for the call stack.